Easy BFS on Grid C++


#1
int dx[8] = {2,2,-2,-2,1,1,-1,-1};
int dy[8] = {1,-1,1,-1,2,-2,2,-2};


bool isValid(int x, int y, int n, int m, vector<vector<int>>& vis)
{
    if(x<0 || y<0 || x>=n || y>=m) return false;
    if(vis[x][y]==1) return false;
    return true;
}


int Solution::knight(int n, int m, int sx, int sy, int ex, int ey) {
    if(sx==ex && sy==ey) return 0;
    vector<vector<int>> vis(n, vector<int>(m,0));
    sx -= 1;
    sy -= 1;
    ex -= 1;
    ey -= 1;

queue<array<int,3>> q;
q.push({sx,sy,0});
vis[sx][sy] = 1;

while(!q.empty())
{
    array<int,3> curr = q.front();
    q.pop();
    int x = curr[0], y = curr[1], d = curr[2];
    if(x==ex && y==ey) return d;
    for(int i=0;i<8;i++)
    {
        int xnew = x + dx[i], ynew = y + dy[i];
        if(isValid(xnew,ynew,n,m,vis)) 
        {
            vis[xnew][ynew] = 1;
            q.push({xnew,ynew,d+1});
        }
    }
}
return -1;

}