We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Search
  4. KnightL on a Chessboard
  5. Discussions

KnightL on a Chessboard

  • unreal031008
     + 0 comments

    For every position,the Knight has at most 8 directions to go.Therfore, all the positions form a graph that each vertex has at most 8 edges. If we want the Knight move from (0,0) to (n-1,n-1) within the minimum steps, we can use BFS(Breadth-First Search) to enumerate all possibilities. Before we use BFS, we can simplify the situations: Especially, when a==b, we can be certain that the minimum steps that the Knight will take is to move along the diagonal. Thus, the next thing to do is to judge whether (n-1)%a==0 is valid or not. And the result of (n-1)/a is the answer for a==b. Here is my C++ solution.

    C++ solution of Knight on a Chessboard. Thanks for @sumesh1999. I revised and optimized my code after referring to your code.

    int BFS(int i,int j,int n){
    queue<pair<pair<int,int>,int>> q;
    int id[n][n];
    memset(id,0,sizeof(id));
    id[0][0]=1;
    vector<pair<int,int>> move={{i,j},{i,-j},{-i,j},{-i,-j},{j,i},{j,-i},{-j,i},{-j,-i}};
    q.push({{0,0},0});
    
    while(!q.empty()){
        int x=q.front().first.first,y=q.front().first.second,count=q.front().second;
        for(int i=0;i<8;i++){
            int tempx=x+move[i].first,tempy=y+move[i].second;
            if(tempx>=0 && tempy>=0 && tempx<n && tempy<n && id[tempx][tempy]==0){
                q.push({{tempx,tempy},count+1});
                id[tempx][tempy]=1;
            }
        }
        if(x==n-1 && y==n-1)
            return count;
        q.pop();
    }
    return -1;
}

vector<vector<int>> knightlOnAChessboard(int n) {
    int d=n-1;
    vector<vector<int>> ans(d,vector<int>(d,0));
    for(int i=0;i<d;i++){
        for(int j=0;j<d;j++){
            if(i==j){
                if(d%(i+1)==0) ans[i][j]=d/(i+1);
                else ans[i][j]=-1;
            }
            else{
                if(ans[i][j]==0){
                    ans[i][j]=BFS(i+1,j+1,n);
                }
                ans[j][i]=ans[i][j];
            }
        }
    }
    return ans;
}