首页 > 代码库 > 1215 迷宫

1215 迷宫

2024-09-16 09:32:10   218人阅读

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

思路：深搜。
 1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 int map[20][20]; 5 int d[5]={0,1,0,-1,0}; 6 int n,m; 7 char s; 8 void dfs(int a,int b) 9 {10     if(a==m&&b==m)return ;11     for(int i=0;i<4;++i)12     {13         int h=a+d[i];14         int z=b+d[i+1];15         if((h<=m)&&(h>0)&&(z>0)&&(z<=m)&&map[h][z]==0)16         {17             map[h][z]=1;18             dfs(h,z);19         }20     }21 }22 int main()23 {24     cin>>n;25     while(n--)26     {27         memset(map,0,sizeof(map));28         cin>>m;29         for(int i=1;i<=m;++i)30         {31             for(int j=1;j<=m;++j)32             {33                 cin>>s;34                 if(s==‘#‘)map[i][j]=1;35             }36         }37         map[1][1]=1;38         dfs(1,1);39         if(map[m][m])cout<<"YES\n";40         else cout<<"NO\n";41     }42     return 0;43 }

 

1215 迷宫


联系
我们