时间限制: 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
数据范围及提示 Data Size & Hint
裸dfs,注意这个不需要回退
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 const int MAXN=1001;
6 const int maxn=0x7fffffff;
7 int map[MAXN][MAXN];
8 int vis[MAXN][MAXN];
9 int bgx,bgy;
10 int edx,edy;
11 int xx[5]={-1,+1,0,0};
12 int yy[5]={0,0,-1,+1};
13 int n;
14 int m;
15 int flag;
16 void dfs(int x,int y)
17 {
18 if(x==edx&&y==edy)
19 {
20 flag=1;
21 return ;
22 }
23 for(int i=0;i<4;i++)
24 {
25 int wx=x+xx[i];
26 int wy=y+yy[i];
27 if(wx>0&&wx<=m&&wy>0&&wy<=m&&map[wx][wy]!=1&&vis[wx][wy]==0)
28 {
29 vis[wx][wy]=1;
30 dfs(wx,wy);
31 }
32 }
33 }
34 int main()
35 {
36
37 scanf("%d",&n);
38 for(int lll=1;lll<=n;lll++)
39 {
40
41 scanf("%d",&m);
42 memset(vis,0,sizeof(vis));
43 for(int i=1;i<=m;i++)
44 {
45 for(int j=1;j<=m;j++)
46 {
47 char c;
48 //scanf("%c",&c);
49 cin>>c;
50 if(c=='.')map[i][j]=0;
51 else if(c=='#')map[i][j]=1;
52 else if(c=='s')
53 {
54 bgx=i;
55 bgy=j;
56 }
57 else if(c=='e')
58 {
59 edx=i;
60 edy=j;
61 }
62 }
63 }
64 dfs(bgx,bgy);
65 if(flag==1)
66 printf("YES");
67 else
68 printf("NO");
69 }
70
71 return 0;
72 }