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
          
            2 #include
           
             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 }