noj电子老鼠走迷宫(深搜dfs)超时错误

1042.电子老鼠闯迷宫

时限:1000ms 内存限制:10000K  总时限:3000ms

描述
有一只电子老鼠被困在如下图所示的迷宫中。这是一个12*12单元的正方形迷宫,黑色部分表示建筑物,白色部分是路。电子老鼠可以在路上向上、下、左、右行走,每一步走一个格子。现给定一个起点S和一个终点T,求出电子老鼠最少要几步从起点走到终点。
noj电子老鼠走迷宫(深搜dfs)超时错误
 
输入
本题包含一个测例。在测例的第一行有四个由空格分隔的整数,分别表示起点的坐标S(x.y)和终点的坐标T(x,y)。从第二行开始的12行中,每行有12个字符,描述迷宫的情况,其中'X'表示建筑物,'.'表示路.
 
输出
输出一个整数,即电子老鼠走出迷宫至少需要的步数。
 
输入样例
2 9 11 8
XXXXXXXXXXXX
X......X.XXX
X.X.XX.....X
X.X.XX.XXX.X
X.X.....X..X
X.XXXXXXXXXX
X...X.X....X
X.XXX...XXXX
X.....X....X
XXX.XXXX.X.X
XXXXXXX..XXX
XXXXXXXXXXXX
 
输出样例
28
#include <stdio.h>
#include <string.h> int n=,m=,p,q,min = ;
int book[][];
char a[][]; void dfs(int x,int y,int step)
{
int next[][] = {{,},{,},{,-},{-,}}; int tx,ty,k; if (x==p&&y==q)//判断是否到达位置
{
if(step<min)
min = step;
return;
} for (k = ;k <= ;k++)//枚举四种走法
{
tx = x + next[k][];
ty = y + next[k][]; if (tx<||tx>n||ty<||ty>m)//判断是否越界
{
continue;
} if (a[tx][ty]=='.'&&book[tx][ty]==)//判断是否为障碍物和是否在路径中
{
book[tx][ty] = ;
dfs(tx,ty,step+);
book[tx][ty]=;
}
}
return;
} int main()
{
int i,startx,starty; scanf("%d %d %d %d",&startx,&starty,&p,&q); getchar(); for(i=;i<=n;i++)
gets(a[i]); book[startx][starty] = ; dfs(startx,starty,); printf("%d\n",min); return ;
}
上一篇:NumPy的基本用法


下一篇:linux系统编程之进程(八):守护进程详解及创建,daemon()使用