Sicily 1215: 脱离地牢（BFS）

　　这道题按照题意直接BFS即可，主要要注意题意中的相遇是指两种情况：一种是同时到达同一格子，另一种是在移动时相遇，如Paris在（1，2），而Helen在（1，2），若下一步Paris到达（1，1），而Helen达到（1，2），这种情况也算是相遇。

 #include<bits/stdc++.h>

 using namespace std;

 int _move[][] = {{-, }, {, }, {, -}, {, }};

 int visit[][][][];

 int Helen_move[];

 int n,m;

 char _map[][];

 struct Node{

     int x1, y1;//Paris

     int x2, y2;//Helen

     int step;

 };

 Node bfs(int x1, int y1, int x2, int y2, int n, int m){

     Node front;

     front.x1 = x1;

     front.y1 = y1;

     front.x2 = x2;

     front.y2 = y2;

     front.step = ;

     queue<Node> q;

     q.push(front);

     visit[x1][y1][x2][y2] = ;

     while(!q.empty()){

         front = q.front(); q.pop();

         if(front.step > ) {

             return front;//若大于255，则返回

         }

         for(int i = ; i < ; i++){

             int Paris_x = front.x1 + _move[i][];//走一步

             int Paris_y = front.y1 + _move[i][];

             if( <= Paris_x && Paris_x < n &&  <= Paris_y && Paris_y < m &&

                 _map[Paris_x][Paris_y] != '#' && _map[Paris_x][Paris_y] != '!'){

                 int k = Helen_move[i];

                 int Helen_x = front.x2 + _move[k][];

                 int Helen_y = front.y2 + _move[k][];

                 if( <= Helen_x && Helen_x < n &&  <= Helen_y && Helen_y < m){

                     if(_map[Helen_x][Helen_y] == '#'){//撞墙则不走

                         Helen_x = front.x2;

                         Helen_y = front.y2;

                     }

                     else if(_map[Helen_x][Helen_y] == '!') continue;//遇到熔浆

                     if(visit[Paris_x][Paris_y][Helen_x][Helen_y] == ) continue;

                     Node tmp = front;

                     tmp.x1 = Paris_x;

                     tmp.y1 = Paris_y;

                     tmp.x2 = Helen_x;

                     tmp.y2 = Helen_y;

                     tmp.path[tmp.step] = i;

                     tmp.step = front.step + ;

                     q.push(tmp);

                     visit[Paris_x][Paris_y][Helen_x][Helen_y] = ;

                     if(Paris_x == Helen_x && Paris_y == Helen_y){//直接相遇

                         return tmp;

                     }

                     if(Paris_x == front.x2 && Paris_y == front.y2 &&

                        Helen_x == front.x1 && Helen_y == front.y1){

                            return tmp;//交差相遇

                     }

                 }

             }

         }

     }

     front.step = ;

     return front;

 }

 int main(){

     cin >> n >> m;

     int x1, y1;

     int x2, y2;

     memset(visit, , sizeof(visit));

     memset(Helen_move, , sizeof(Helen_move));

     for(int i = ; i < n; i++){

         for(int j = ; j < m; j++){

             cin >> _map[i][j];

             if(_map[i][j] == 'P'){//Paris的位置

                 x1 = i;

                 y1 = j;

             }

             if(_map[i][j] == 'H'){//Helen的位置

                 x2 = i;

                 y2 = j;

             }

         }

     }

     for(int i = ; i < ; i++){

         char c;

         cin >> c;

         if(c == 'N')Helen_move[i] = ;//Paris走时Helen的方向

         else if(c == 'S')Helen_move[i] = ;

         else if(c == 'W')Helen_move[i] = ;

         else if(c == 'E')Helen_move[i] = ;

     }

      Node tmp = bfs(x1, y1, x2, y2, n, m);

     if(tmp.step > ) cout << "Impossible" << endl;

     else{

         cout << tmp.step << endl;

     }

 }

 /*

 5 5

 #####

 #P#.#

 #H!.#

 #.#.#

 #####

 WNSE

 */