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 #include
            
              4 using namespace std; 5 const int N=17; 6 char a[N][N]; 7 int z; 8 int heng[5]={
        0,+1,-1,0,0}; 9 int zong[5]={
        0,0,0,-1,+1};10 int vis[N][N];11 int n;12 int ans;13 void  dfs(int x,int y)14 {15     if(x==n&&y==n)16      {17          ans=1;18          return ;19      }20     for(int i=1;i<=4;i++)21      {22          int xx=x+heng[i];23          int yy=y+zong[i];24          if(xx>0&&xx<=n&&yy>0&&yy<=n&&vis[xx][yy]==0&&a[xx][yy]!='#')25           {26               vis[xx][yy]=1;27               dfs(xx,yy);28           }29      }30 }31 int main()32 {33     cin>>z;34     for(int k=1;k<=z;k++)35      {         36          cin>>n;37          for(int i=1;i<=n;i++)38           {39               for(int j=1;j<=n;j++)40                {41                    cin>>a[i][j];42                }43           }44         dfs(1,1);45          if(ans==1)46           {47               cout<<"YES";48                   }        49          else50          {51              cout<<"NO";52          }53      }54      return 0;55 }