1 #include
     
        2 using namespace std;  3    4 struct Node  5 {  6     int c,r,g;  7     Node(int c,int r,int g): c(c),r(r),g(g) {}  8     Node() {}  9 }; 10   11 const int maxn = 12; 12   13 int N,M,T; 14 int c1,r1,g1; 15 int c2,r2,g2; 16 int m[11][11][2]; 17 int d[11][11][2]; 18   19 void read() 20 { 21     char tmp; 22     for(int k = 0; k < 2; k ++) 23     { 24         for(int i = 0; i < N; i ++) 25         { 26             for(int j = 0; j < M; j ++) 27             { 28                 cin >> tmp; 29                 if(tmp=='S') 30                 { 31                     c1 = i; 32                     r1 = j; 33                     g1 = k; 34                 } 35                 else if(tmp=='.') 36                     m[i][j][k] = 0; 37                 else if(tmp=='*') 38                     m[i][j][k] = 1; 39                 else if(tmp=='#') 40                     m[i][j][k] = 2; 41                 else if(tmp=='P') 42                 { 43                     c2 = i; 44                     r2 = j; 45                     g2 = k; 46                 } 47             } 48         } 49         string tmp; 50         getline(cin,tmp); 51     } 52     for(int k = 0; k < 2; k ++) 53         for(int i = 0; i < N; i ++) 54             for(int j = 0; j < M; j ++) 55                 if((m[i][j][k]==2||m[i][j][k]==1) && m[i][j][k^1]==2) 56                     m[i][j][k^1] = m[i][j][k] = 1; 57 } 58   59 const int dr[] = {
   0,-1,1,0}; 60 const int dc[] = {
   1,0,0,-1}; 61   62 Node walk(const Node& u,int i) 63 { 64     return Node(u.c+dc[i],u.r+dr[i],u.g); 65 } 66   67 int inside(const Node& v) 68 { 69     return v.c>=0&&v.c
      
       =0&&v.r
       
         q; 75     memset(d,-1,sizeof(d)); 76     d[c1][r1][g1] = 0; 77     q.push(Node(c1,r1,g1)); 78     while(!q.empty()) 79     { 80         Node u = q.front(); 81         q.pop(); 82         if(m[c1][r1][g1]==2&&c1==c2&&r1==r2 83         || u.c==c2&&u.r==r2&&u.g==g2)   return d[c2][r2][g2]; 84         for(int i = 0; i < 4; i ++) 85         { 86             Node v = walk(u,i); 87             if(inside(v) && m[v.c][v.r][v.g] != 1 88                     && d[v.c][v.r][v.g] < 0) 89             { 90                 if(m[v.c][v.r][v.g]==2) 91                 { 92                     d[v.c][v.r][v.g] = d[u.c][u.r][u.g] + 1; 93                     d[v.c][v.r][v.g^1] = d[u.c][u.r][u.g] + 1; 94                     v.g ^= 1; 95                     q.push(v); 96                 } 97                 else if(m[v.c][v.r][v.g]==0) 98                 { 99                     d[v.c][v.r][v.g] = d[u.c][u.r][u.g] + 1;100                     q.push(v);101                 }102             }103         }104     }105     return 393939;106 }107  108 int main()109 {110 //  int A;111 //  cin >> A;112     while(cin >> N >> M >> T)113     {114         c1 = r1 = g1 = 0;115         read();116         int rnt = solve();117     //  cout << rnt << endl;118         if(rnt <= T)119             cout << "YES" << endl;120         else121             cout << "NO" << endl;122     }123     return 0;124 }
       
      
     

BFS