1215 迷宫

时间限制: 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

分类标签 Tags 点此展开

裸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 }