输入样例:
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] |