问题 AC: 中国象棋中的跳马问题

问题 AC: 中国象棋中的跳马问题
时间限制: 5 Sec 内存限制: 128 MB
题目描述
现在棋盘的大小不一定，由p，q给出，并且在棋盘中将出现障碍物（限制马的行动，与象棋走法相同）
输入
第一行输入n表示有n组测试数据。
每组测试数据第一行输入2个整数p,q，表示棋盘的大小(1<=p,q<=100)。
每组测试数据第二行输入4个整数，表示马的起点位置与终点位置。(位置的取值范围同p,q)
第三行输入m表示图中有多少障碍。
接着跟着m行，表示障碍的坐标。

输出
马从起点走到终点所需的最小步数。
如果马走不到终点，则输入“can not reach!”
样例输入

2
9 10
1 1 2 3
0
9 10
1 1 2 3
8
1 2
2 2
3 3
3 4
1 4
3 2
2 4
1 3

样例输出

1
can not reach!

提示
此题是一个搜索题，建议选择BFS(广搜)。一开始把马的起始点加入队列，然后用广搜的思想把此点能到达的其他点加入队列，这里需要一个数组用来记录此点在之前是否已经加入队列，如果加入过队列当中，就不需要再加入了，直到队列里的元素为空，或者搜索到了终点，搜索即停止，然后输出相应答案即可。

学校oj，典型的BFS题目。
如提示所言，我们把起始点加入队列，然后枚举扩展马的八个方向，将符合条件的点加入队列直到搜遍所有可能或者到达终点
那么如何得到最短步数呢 ，
BFS其实就和层次遍历差不多，事实上知道遍历到了第几层，就知道了答案
可以考虑用一个辅助队列存储一层的可能性，q1.用q来作为主搜索队列，用一个标记来表示到了哪一层，如：起点进队列q，标志进队列q.
这时候由起点的得到的扩展（八个方向）先不放进q，而是放到q1暂时存储。起点便是第一层，然后遇到了标记，此时将q1中的点全部放到q中，作为第二层，然后再push一个标记,遍历时，第二层可以扩展到的点加入q1，作为第三层，以此类推。细节代码如下

这里我用的2来表示有障碍物，1来表示已经遍历过了，0为初始状态
dx数组和dy数组表示八个方向的扩展。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int v[102][102];

#define endl "\n"

int check(int x,int y,int i)
{
    
    if(i==0|i==1){
    
        if(v[x+1][y]==2)return 0;
        else return 1;
    }else if(i==4||i==2){
    
        if(v[x][y+1]==2)return 0;
        else return 1;
    }else if(i==6||i==7){
    
        if(v[x-1][y]==2)return 0;
        else return 1;
    }else if(i==3||i==5){
    
        if(v[x][y-1]==2)return 0;
        else return 1;
    }
}

void init(int m,int n)
{
    
    for(int i=0;i<=m;++i){
    
        for(int j=0;j<=n;++j)v[i][j]=0;
    }
}

int main()
{
    
    int t= 1;
    cin>>t;
    while(t--){
    
        int p,Q;
        cin>>p>>Q;
        pair<int,int>star;
        pair<int,int>End;
        cin>>star.first>>star.second;
        cin>>End.first>>End.second;

        init(p,Q);//初始化v数组

        //cout<<" 输入的终点为："<<End.first<<" "<<End.second<<endl;
        int m;
        cin>>m;
        int dx[8]={
    2,2,1,1,-1,-1,-2,-2},dy[8]={
    1,-1,2,-2,2,-2,1,-1};//枚举跳马的八种可能
        while(m--){
    //障碍物
            int x,y;
            cin>>x>>y;
            v[x][y]=2;
        }
        queue<pair<int,int>> q;
        queue<pair<int,int>> q1;
        q.push(star);
        v[star.first][star.second]=1;//搜过了
        q.push({
    0,0});
        int ans = 0 , flag=0;

        while(q.size()){
    
            auto t= q.front();
            q.pop();//取出队头元素

            //特判遇到终点
            if(t.first==End.first&&t.second==End.second){
    
                flag=1;
                break;
            }

            if(t.first==0&&t.second==0){
    //当遇到标记时 将临时队列的所有元素搬到主队列
                ans++;//更新答案
                if(q1.size()==0){
    
                    break;
                }
                while(q1.size()){
    
                    q.push(q1.front());
                    q1.pop();
                }
                q.push({
    0,0});//将分割标志进队
                continue;
            }

            //扩展马的八种走法，合理的就加入临时队列
            for(int i=0;i<8;++i){
    
                int x=t.first+dx[i];
                int y=t.second+dy[i];
                if(v[x][y]!=0)continue;//搜过的跳过,有障碍的跳过
                if(x>0&&x<=p&&y>0&&y<=Q&&check(t.first,t.second,i)){
    
                    q1.push({
    x,y});
                    v[x][y]=1;//进队并且标记
                }
            }
        }
        if(flag)cout<<ans<<"\n";
        else cout<<"can not reach!\n";

    }
    return 0;
}

大概这样，溜了
若有错误，大佬指正