POJ1915 Knight Moves

╰半夏微凉° 2022-06-12 12:08 108阅读 0赞

#include <iostream> //结果正确，提交AC
    #include <cstdio>   //统计最小步数（故用BFS，直接对应最短路）
    #include <queue>
    #include <cstring>
    using namespace std;
    
    const int MAXN = 100000 + 10;
    int n, sx, sy, ex, ey;
    int vis[310][310];
    int dir[8][2] = {1, -2, 2, -1, 2, 1, 1, 2,-1, -2, -2, -1, -2, 1, -1, 2};   //结果与 此遍历顺序无关
    struct node{
        int x;
        int y;
        int step;
    };
    
    int judge(int x, int y)
    {
        if(vis[x][y]==1 ||x < 0 || x >= n || y < 0 || y >= n)
            return 1 ;
        return 0;
    }
    
    void bfs()
    {
        queue<node>Q;
        node  now, next;
        now.x = sx;
        now.y = sy;
        now.step = 0;
    
        Q.push(now);
        vis[sx][sy] = 1;
    
        while(!Q.empty()){
            now = Q.front();
            Q.pop();
            if(now.x == ex && now.y == ey){
                cout << now.step << endl;
                return;
            }
            for(int i = 0 ; i < 8 ; i++){
                next.x = now.x + dir[i][0];
                next.y = now.y + dir[i][1];
                if( judge(next.x, next.y) )
                    continue;
                next.step = now.step + 1;
                Q.push(next);
                vis[next.x][next.y] = 1;
            }
        }
    }
    int main()
    {
        int T ;
        cin >> T;
        while(T--){
            memset(vis,0,sizeof(vis));//每用一次都要置零
            scanf("%d%d%d%d%d",&n,&sx,&sy,&ex,&ey);
            bfs();
        }
        return 0;
    }
    
    //input的第一行是样例的个数，
    //第二行是棋盘的大小，第三行是起点第四行是终点