输入样例:
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>
#define MAX 99999999
int a[51][51];
int book[51][51];
int n,m,sx,sy,ex,ey;
int min=MAX;
void dfs(int x ,int y,int s)
{
//到达目标
if(x==ex && y==ey)
{
//最小值更新
if(s<=min)
min=s;
//这个地方一要记得返回
return;
}
//边界剪枝
if( x < 1 || x > n || y < 1 || y > m)
return ; //每个剪枝一定要返回
//判断是否是墙 以及 是否已经走过
if(a[x][y]==1 || book[x][y]==1)
return ;//每个剪枝一定要返回
book[x][y]=1;//开始走,标记一下,这里标记一下就代表走完了,有的题目还需要其他的操作
//接下来尝试朝四个方向走
dfs(x,y+1,s+1);
dfs(x,y-1,s+1);
dfs(x+1,y,s+1);
dfs(x-1,y,s+1);
//将刚刚走的标记为没有走,也就是还原
book[x][y]=0;
return ;
}
int main()
{
int i,j;
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
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",&sx,&sy,&ex,&ey);
//从猫的起点开始深度搜素
dfs(sx,sy,0);
if(min==MAX)
printf("-1");
else
printf("%d",min);
return 0;
}
</stdio.h>[/code] |