只有bfs函数中中间那小段循环不一样。其他都一样。


题目是马踏棋盘。两点最短步数。。l是棋盘宽度。x1 y1 是起始点，x2 y2是中点
为什么我想来想去中间那段都是等价的。。为什么第一个广搜有些数据他就崩呢。。比如 l=100 起点 0 0 中点 30 50
#include<iostream>
#include<queue>
using namespace std;

typedef struct
{
    int x,y;
    int step;
}Node;

int x1,y1,x2,y2;
int l;
int visit[400][400];
int X[8]={1,1,-1,-1,2,2,-2,-2};
int Y[8]={2,-2,2,-2,1,-1,1,-1};
void bfs()
{
    Node A,B;
    int a,dx,dy;

    queue<Node>q;
    A.step=0;
    A.x=x1;
    A.y=y1;
    q.push(A);

    while(!q.empty())
    {
        A=q.front();
        visit[A.x][A.y]=1;
        if(A.x==x2&&A.y==y2) break;
        else
        {

            for(a=0;a<8;a++)
            {
                dx=A.x+X[a];
                dy=A.y+Y[a];
                if(dx<l&&dy<l&&dx>=0&&dy>=0&&visit[dx][dy]==0)
                {
                    visit[dx][dy]=1;
                    B.x=dx;
                    B.y=dy;
                    B.step=A.step+1;
                    q.push(B);
                }

            }
        }
        q.pop();
    }
    cout<<A.step<<endl;
}

int main()
{
    int n;
    int a,b,c;
    cin>>n;
    for(a=0;a<n;a++)
    {
        for(b=0;b<400;b++)
            for(c=0;c<400;c++)
            {
                visit[b][c]=0;
            }
        cin>>l;
        cin>>x1>>y1;
        cin>>x2>>y2;
        bfs();
    }
}



第二个
#include<iostream>
#include<queue>
using namespace std;

typedef struct
{
    int x,y;
    int step;
}Node;

int x1,y1,x2,y2;
int l;
int visit[400][400];
void bfs()
{
    Node A,B;
    int a,b,dx,dy;

    queue<Node>q;
    A.step=0;
    A.x=x1;
    A.y=y1;
    q.push(A);
    while(!q.empty())
    {
        A=q.front();
        visit[A.x][A.y]=1;
        if(A.x==x2&&A.y==y2) break;
        else
        {
            for(a=-2;a<=2;a=a+4)
                for(b=-1;b<=1;b=b+2)
                {
                    dx=A.x+a;
                    dy=A.y+b;
                    if(dx>=0&&dx<l&&dy>=0&&dy<l&&visit[dx][dy]==0)
                    {
                        B.x=dx;
                        B.y=dy;
                        B.step=A.step+1;
                        q.push(B);
                    }
                }
            for(a=-1;a<=1;a=a+2)
                for(b=-2;b<=2;b=b+4)
                {
                    dx=A.x+a;
                    dy=A.y+b;
                    if(dx>=0&&dx<l&&dy>=0&&dy<l&&visit[dx][dy]==0)
                    {
                        B.x=dx;
                        B.y=dy;
                        B.step=A.step+1;
                        q.push(B);
                    }
                }
        }
        q.pop();
    }
    cout<<A.step<<endl;
}

int main()
{
    int n;
    int a,b,c;
    cin>>n;
    for(a=0;a<n;a++)
    {
        for(b=0;b<400;b++)
            for(c=0;c<400;c++)
            {
                visit[b][c]=0;
            }
        cin>>l;
        cin>>x1>>y1;
        cin>>x2>>y2;
        bfs();
    }
}