周六900C++班级2022-11-12-搜索练习

Knight Moves

#include<bits/stdc++.h>
using namespace std;
int nex[8][2] = {{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2}}; //方向数组
int vis[310][310]; //标记数组
int n,m,f,ans,sx,sy,ex,ey;
struct node{
    int x,y,step; //step步长 
}; 
node q[90005];
void bfs(int sx,int sy)
{
    int head = 1,tail = 1; //队首head，队尾tail
    q[tail].x = sx;
    q[tail].y = sy;
    q[tail].step = 0; //13行-15行：起点入队
    tail++; //队尾扩充 
    vis[sx][sy] = 1; //标记起点
    while(head<tail)
    {
        for(int i=0;i<8;i++) //循环队首head的8个方向
        {
            int tx = nex[i][0] + q[head].x; //下一步坐标tx = 第i个方向+队首head的x坐标
            int ty = nex[i][1] + q[head].y;
            if(tx<0||tx>=n||ty<0||ty>=n)continue;
            if(vis[tx][ty]==0) //tx,ty没有标记过
            {
                //标记入队并扩充队列长度 
                vis[tx][ty] = 1;
                q[tail].x = tx;
                q[tail].y = ty;
                q[tail].step = q[head].step + 1;
                tail++; 
            } 
            if(tx==ex && ty==ey){ //判断下一步是否是终点 
                f = 1; //终点标记f = 1
                ans = q[tail-1].step;
                break; 
            }
        }
        if(f)break;
        head++;
    }
}
int main()
{
    int t; //t组数据
    cin>>t;
    while(t--) //处理t组数据 
    {
        cin>>n>>sx>>sy>>ex>>ey; //输入地图大小和起点终点
        memset(vis,0,sizeof(vis)); //初始化标记数组为0 
        f = 0;ans = 0;
        if(sx==ex && sy==ey){ //起点为终点 
            cout<<0<<endl;
            continue;
        } 
        bfs(sx,sy); //将起点传入开搜
        cout<<ans<<endl;
    } 
     return 0;
}