只有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();
    }
}

你说第一个程序有问题，然而，我就复制了你的第二个程序。。
然后用了100 0 0 30 50的案例测试，中间加了一个输出检测。。。程序就开始无休止的跑循环了。
这如果是个编程题，那你绝对是超时了（截止写评论时已经跑了一分钟了，没完）。。。

1.广、深度优先搜索不长这样，你的visit[][]=1放错位置了，应该是在入栈的时候就把它标记为已经踩过的。否则，同一个坐标会重复入栈，
2.这道题并不是非得用广度优先搜索，为什么。给我两个坐标。（0,0,）（30，50）,每次规定必须走日，我们完全可以通过小学数学的方法计算出所需的步数。
30-0=30//横坐标上右移30个长度，也就需要15个横着的日
50-0-15*1=35//到这一步时我的横坐标就和目的地一样了，纵坐标方向差35，
35/2=17...1//经过偶数个日后我们将到达（30,49）或者（29,50），最短路径就这两条。可以论证的
后退一步到（29,47），经（28,49）到达（30.50）
总的就是15+17+1=33
 当然了，从这个思想出发你需要不停地计算单双，考虑各种情况。如果你可以思虑完整，你的程序时间复杂度只有O（1）。不过忙费脑子的就是了

3.那么还是要广搜的话，我个人建议你加一个小函数，用来计算两个坐标间的距离，比如像（10,10）出发到（30,50）那么第一步应该去的坐标只有（12,11）（11,12），其他六个方向都不用去。而我们要判断这个只要计算一下坐标差就行了比如：（12,11）30-12+50-11<30-10+50-10;标记，入栈；然而像（8,11）30-8+50-11>30-10+50-10;标记，但不入栈。

[此贴子已经被作者于2016-7-14 10:37编辑过]