时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
在N*N的迷宫内，“#”为墙，“.”为路，“s”为起点，“e”为终点，一共4个方向可以走。从左上角（(0,0)“s”）位置处走到右下角（(n-1,n-1)“e”）位置处，可以走通则输出YES，不可以走则输出NO。
输入描述 Input Description
输入的第一行为一个整数m，表示迷宫的数量。 其后每个迷宫数据的第一行为一个整数n（n≤16），表示迷宫的边长，接下来的n行每行n个字符，字符之间没有空格分隔。
输出描述 Output Description
输出有m行，每行对应的迷宫能走，则输出YES，否则输出NO。
样例输入 Sample Input
1 7 s...##. .#..... ....... ..#.... ..#...# ###...# ......e
样例输出 Sample Output
YES
代码：
（使用递归回溯）超时程序：
#include
using namespace std;
#include
#include
int m,p[17][17];
int xx[4]={1,-1,0,0};
int yy[4]={0,0,1,-1};int flag;
void search(int xq,int yq,int xz,int yz,int n)
{
if(xq==xz&&yq==yz)
{
flag=1;
return;
}
for(int i=0;i<=3;++i)
{
int x1=xq+xx[i],y1=yq+yy[i];
if(x1>=1&&x1<=n&&y1>=1&&y1<=n&&p[x1][y1]==0)
{
p[x1][y1]=1;
search(x1,y1,xz,yz,n);
p[x1][y1]=0;
if(flag==1)
return;
}
}
}
int main()
{
scanf("%d",&m);
for(int i=1;i<=m;++i)
{
int n,xq,yq,xz,yz;
scanf("%d",&n);
flag=0;
char bz[17];
memset(p,0,sizeof(p));
for(int j=1;j<=n;++j)
{
scanf("%s",bz+1);
for(int l=1;l<=n;++l)
{
if(bz[l]=='#')
p[j][l]=1;
if(bz[l]=='.')
p[j][l]=0;
if(bz[l]=='s')
{
p[j][l]=0;
xq=l;yq=j;
}
if(bz[l]=='e')
{
p[j][l]=0;
xz=l;
yz=j;
}
}
}
search(xq,yq,xz,yz,n);
if(flag==1)
printf("YES\n");
else printf("NO\n");
}
return 0;
}
AC程序：（广搜加队列）：
#include
using namespace std;
#include
#include
int d[17*17][2]={0},head,tail,mg[17][17]={0};
int xx[]={0,0,1,-1};
int yy[]={1,-1,0,0},m;
int search(int n,int xz,int yz)
{
head=0;tail=1;
memset(d,0,sizeof(d));
d[tail][0]=1;d[tail][1]=1;
mg[1][1]=1;
while(head
{
++head;
int x1=d[head][0],y1=d[head][1];
if(x1==xz&&y1==yz)
return 1;
for(int i=0;i<=3;++i)
{
int x=x1+xx[i],y=y1+yy[i];
if(x>=1&&x<=n&&y>=1&&y<=n&&mg[x][y]==0)
{
++tail;
d[tail][0]=x;
d[tail][1]=y;
mg[x][y]=1;
}
}
}
return 0;
}
void input()
{
char p[17];
scanf("%d",&m);
int xq=1,xz,n,yq=1,yz;
mg[1][1]=1;
for(int i=1;i<=m;++i)
{
scanf("%d",&n);
xz=n;yz=n;
for(int l=1;l<=n;++l)
{
scanf("%s",p+1);
for(int j=1;j<=n;++j)
{
if(p[j]=='#')
mg[l][j]=1;
}
}
int flag=search(n,xz,yz);
if(flag==1) printf("YES\n");
else printf("NO\n");
}
}
int main()
{
input();
return 0;
}