bfs HDU2102

  1 #include <iostream>
  2 #include <fstream>
  3 #include <map>
  4 #include <cstring>
  5 #include <cstdio>
  6 #include <cstdlib>
  7 #include <queue>
  8 
  9 using namespace std;
 10 
 11 char arr[2][15][15];
 12 int time;
 13 int flag;
 14 int visited[2][15][15];
 15 
 16 void dfs(int r,int x,int y,int cnt)
 17 {
 18     if(flag)
 19         return ;
 20     if(cnt>time)
 21         return ;
 22     if(arr[r][x][y]=='P')
 23     {
 24         flag=1;
 25         return ;
 26     }
 27 //    system("pause");
 28 //    cout<<r<<" "<<x<<" "<<y<<" "<<cnt<<endl;
 29     if(visited[r][x+1][y]==0)
 30     {
 31         if(arr[r][x+1][y]=='.')
 32         {
 33             visited[r][x+1][y]=1;
 34             dfs(r,x+1,y,cnt+1);
 35             visited[r][x+1][y]=0;
 36         }
 37         else if(arr[r][x+1][y]=='#')
 38         {
 39             visited[1-r][x+1][y]=1;
 40             dfs(1-r,x+1,y,cnt+1);
 41             visited[1-r][x+1][y]=0;
 42         }
 43         else if(arr[r][x+1][y]=='P')
 44         {
 45             visited[r][x+1][y]=1;
 46             dfs(r,x+1,y,cnt+1);
 47             visited[r][x+1][y]=0;
 48         }
 49     }
 50     if(visited[r][x][y+1]==0)
 51     {
 52         if(arr[r][x][y+1]=='.')
 53         {
 54             visited[r][x][y+1]=1;
 55             dfs(r,x,y+1,cnt+1);
 56             visited[r][x][y+1]=0;
 57         }
 58         else if(arr[r][x][y+1]=='#')
 59         {
 60             visited[1-r][x][y+1]=1;
 61             dfs(1-r,x,y+1,cnt+1);
 62             visited[1-r][x][y+1]=0;
 63         }
 64         else if(arr[r][x][y+1]=='P')
 65         {
 66             visited[r][x][y+1]=1;
 67             dfs(r,x,y+1,cnt+1);
 68             visited[r][x][y+1]=0;
 69         }
 70     }
 71     if(visited[r][x-1][y]==0)
 72     {
 73         if(arr[r][x-1][y]=='.')
 74         {
 75             visited[r][x-1][y]=1;
 76             dfs(r,x-1,y,cnt+1);
 77             visited[r][x-1][y]=0;
 78         }
 79         else if(arr[r][x-1][y]=='#')
 80         {
 81             visited[1-r][x-1][y]=1;
 82             dfs(1-r,x-1,y,cnt+1);
 83             visited[1-r][x-1][y]=0;
 84         }
 85         else if(arr[r][x-1][y]=='P')
 86         {
 87             visited[r][x-1][y]=1;
 88             dfs(r,x-1,y,cnt+1);
 89             visited[r][x-1][y]=0;
 90         }
 91     }
 92     if(visited[r][x][y-1]==0)
 93     {
 94         if(arr[r][x][y-1]=='.')
 95         {
 96             visited[r][x][y-1]=1;
 97             dfs(r,x,y-1,cnt+1);
 98             visited[r][x][y-1]=0;
 99         }
100         else if(arr[r][x][y-1]=='#')
101         {
102             visited[1-r][x][y-1]=1;
103             dfs(1-r,x,y-1,cnt+1);
104             visited[1-r][x][y-1]=0;
105         }
106         else if(arr[r][x][y-1]=='P')
107         {
108             visited[r][x][y-1]=1;
109             dfs(r,x,y-1,cnt+1);
110             visited[r][x][y-1]=0;
111         }
112     }
113 }
114 
115 int main()
116 {
117     int T;
118     scanf("%d",&T);
119     while(T--)
120     {
121         int n,m;
122         flag=0;
123         memset(arr,'*',sizeof(arr));
124         memset(visited,0,sizeof(visited));
125         scanf("%d%d%d",&n,&m,&time);
126         for(int i=0;i<=1;i++)
127         {
128             for(int j=0;j<n;j++)
129             {
130                 scanf("%s",&arr[i][j]);
131             }
132         }
133         for(int i=0;i<=1;i++)
134         {
135             for(int j=0;j<n;j++)
136             {
137                 for(int t=0;t<m;t++)
138                 {
139                     if(arr[i][j][t]=='#')
140                     {
141                         if(arr[1-i][j][t]=='*'||arr[1-i][j][t]=='#')
142                             arr[i][j][t]='*';
143                     }
144                 }
145             }
146         }
147         dfs(0,0,0,0);
148         if(flag)
149             cout<<"YES"<<endl;
150         else
151             cout<<"NO"<<endl;
152     }
153     return 0;
154 }
View Code