[图论]-BFS(hellokitty抓米奇)

啊哈磊

输入样例：
4 5
0 0 0 0 0
0 1 0 0 0
0 0 1 1 0
1 0 0 0 0
2 5
4 3

注：第一行两个数分别表示迷宫的长和宽
接下来是具体的迷宫，1是墙，0是可以走的地方
在接下来是hellokitty的坐在坐标
在接下来是米奇的坐标

输出样例：
4

代码：

[code=Cpp width=740px]#include <stdio.h>
struct  note
{
    int x;//横坐标
    int y;//纵坐标
    int f;//父亲节点在队列中的编号，本题不要求输出路径，可以不需要f
    int s;//步数
};
int main()
{   
    struct note que[2501];
    int a[51][51]={0},book[51][51]={0};
    //定义一个用于表示走的方向的数组
    int next[4][2]={{ 0, 1},//向右走
                    { 1, 0},//向下走
                    { 0,-1},//向左走
                    {-1, 0}};//向上走
    int top,bottom;
    int i,j,k,n,m,x1,y1,x2,y2,tx,ty,flag;
   
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            scanf("%d",&a[j]);
    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
   
    //队列初始化
    top=1;
    bottom=0;
    //往队列插入第一个节点，猫的位置
    bottom++;
    que[bottom].x=x1;
    que[bottom].y=y1;
    que[bottom].f=0;
    que[bottom].s=0;
   
    flag=0;//用来标记是否到达目标节点,0表示暂时还没有到达，1表示到达
    //当队列不为空的时候循环
    while(top<=bottom)
    {
        //枚举4种走法
        for(k=0;k<=3;k++)
        {
            //每种尝试走的下一个节点坐标
            tx=que[top].x+next[k][0];
            ty=que[top].y+next[k][1];
            //判断是否越界
            if(tx<1 || tx>n || ty<1 || ty>m)
                continue;
            //判断是否围墙或者曾今走过
            if(a[tx][ty]==0 && book[tx][ty]==0)
            {
                //把这个点标记为已经走过
                //注意宽搜每个节点只入队一次，所以和深搜不同，不需要将book数组还原
                book[tx][ty]=1;
                //插入新的节点到队列中
                bottom++;
                que[bottom].x=tx;
                que[bottom].y=ty;
                que[bottom].f=top;//因为这个节点是从top扩展出来的，所以他的父亲是top
                que[bottom].s=que[top].s+1;//步数是父亲的步数+1
            }
            //如果到老鼠的那个节点了，停止扩展，任务结束，退出循环
            if(tx==x2 && ty==y2)
            {
                //注意下面两句话的位置千万不要写颠倒了,否则就不work了
                flag=1;
                break;
            }
        }
        if(flag==1)
            break;
        top++;//注意这地方千万不要忘记，当一个点扩展结束后，top+1，再通过后面的点再进行扩展
    }
   
    //打印队列中最后一个节点的步数,这个节点肯定是整个队列中第一个，也是唯一的一个老鼠的位置
    printf("%d",que[bottom].s);
    return 0;
}
[/code]