sicily 1215 脱离地牢

Description

在一个神秘的国度里，年轻的王子Paris与美丽的公主Helen在一起过着幸福的生活。他们都随身带有一块带磁性的阴阳魔法石，身居地狱的魔王Satan早就想得到这两块石头了，只要把它们熔化，Satan就能吸收其精华大增自己的魔力。于是有一天他趁二人不留意，把他们带到了自己的地牢，分别困在了不同的地方。然后Satan念起了咒语，准备炼狱，界时二人都将葬身于这地牢里。

危险！Paris与Helen都知道了Satan的意图，他们要怎样才能打败魔王，脱离地牢呢？Paris想起了父王临终前留给他的备忘本，原来他早已料到了Satan的野心，他告诉Paris只要把两块魔法石合在一起，念出咒语，它们便会放出无限的光亮，杀死魔王，脱离地牢，而且本子上还附下了地牢的地图，Paris从中了解到了Helen的位置所在。于是他决定首先要找到Helen，但是他发现这个地牢很奇怪，它会增强二人魔法石所带磁力的大小，而且会改变磁力的方向。这就是说，每当Pairs向南走一步，Helen有可能会被石头吸引向北走一步。而这个地狱布满了岩石与熔浆，Pairs必须十分小心，不仅他不能走到岩石或熔浆上，而且由于他行走一步，Helen的位置也会改变，如果Helen碰到岩石上，那么她将停留在原地，但如果Helen移动到了熔浆上，那么她将死去，Paris就找不到她了。

Pairs仔细分析了地图，他找出了一条最快的行走方案，最终与Helen相聚。他们一起念出了咒语"@^&#……%@%&$"，轰隆一声，地牢塌陷了，他们又重见光明……

Input

输入数据第一行为两个整数n,m（3<=n,m<=20），表示地牢的大小，n行m列。接下来n行，每行m个字符，描述了地牢的地图，"."代表通路，"#"代表岩石，"!"代表熔浆。输入保证地牢是封闭的，即四周均是均是岩石或熔浆。接下来一行有四个字符"N"（北），"S"（南），"W"（西），"E"（东）的排列，表示Paris分别向NSWE四个方向走时Helen受磁石磁力影响的移动方向。

Output

输出文件只有一行，如果Paris能找到Helen，输出一整数d，为Paris最少需要行走的步数；如果Paris在255步之后仍找不到Helen，则输出"Impossible"。注意相遇是指Paris与Helen最终到达同一个格子，或者二人在相邻两格移动后碰在了一起，而后者的步数算他们移动后的步数。

Sample Input

5 5
#####
#H..#
#.!.#
#.#P#
#####
WNSE

Sample Output

5

解释：Paris行走方案为NNWWS，每步过后Helen位置在(2,2), (2,2), (3,2), (4,2), (3,2)。

分析：

本题是经典的迷宫问题，但是很特殊的是本题中有两个同时移动元素，而解决迷宫问题的广搜方法需要记录的是每一步的状态，所以本题的重点其实是在状态的明确上。本题看似可以用Paris一个人的状态来记录，但是其实会产生问题，如果Paris不访问他已经访问的点，会丢失部分状态，因为他访问同一个点并不代表Helen也会走同样的路线。所以，状态应该以两人的位置组合为标志，同时要注意状态的处理和判断，那么几点是否访问的记录数组应该是思维的。另外，注意两人可能相撞的情况只当两人相邻，并且各自走到对方的上一步节点才可能。

代码：

  1 // Problem#: 1215
  2 // Submission#: 1854023
  3 // The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
  4 // URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
  5 // All Copyright reserved by Informatic Lab of Sun Yat-sen University
  6 #include <iostream>
  7 #include <queue>
  8 #include <cstring>
  9 using namespace std;
 10 
 11 #define MAX 20
 12 int n, m;
 13  
 14 struct state{
 15     int P_x, P_y, H_x, H_y;
 16     int step;
 17     bool same(){
 18         return P_x == H_x && P_y == H_y;
 19     }
 20     bool judge(){
 21         return P_x > 0 && P_x <= n &&  P_y > 0 && P_y <= m
 22         && H_x > 0 && H_x <= n && H_y > 0 && H_y <= m ;
 23     }
 24     bool ismeet(state s){
 25         return P_x == s.H_x && P_y == s.H_y && H_x == s.P_x && H_y == s.P_y;
 26     }
 27     state(int P_x, int P_y, int H_x, int H_y) {
 28         this->H_x = H_x; this->H_y = H_y; this->P_x = P_x; this->P_y = P_y; step = 0;
 29     }
 30     state() {
 31         step = 0;
 32     }
 33 };
 34  
 35 enum direction{N, S, W, E};
 36  
 37 int move[4][2] = {{-1, 0},{1, 0}, {0, -1}, {0, 1}};
 38 int match[4];
 39 char _mape[MAX][MAX];
 40 bool visit[MAX][MAX][MAX][MAX];
 41  
 42 int P_x, P_y, H_x, H_y;
 43  
 44 void bfs();
 45  
 46 int main(){
 47     char c;
 48     while (cin >> n >> m){
 49         memset(visit, false, sizeof(visit));
 50  
 51         for (int i = 1; i <= n; i++) 
 52             for (int j = 1; j <= m; j++){
 53                 cin >> _mape[i][j];
 54                 if (_mape[i][j] == 'P'){
 55                     P_x = i;
 56                     P_y = j;
 57                     _mape[i][j] = '.';
 58                 }
 59                 if (_mape[i][j] == 'H'){
 60                     H_x = i;
 61                     H_y = j;
 62                     _mape[i][j] = '.';
 63                 }
 64             }
 65  
 66             for (int i = 0; i < 4; i++){
 67                 cin >> c;
 68                 switch (c){
 69                 case 'N':
 70                     match[i] = N;
 71                     break;
 72                 case 'S':
 73                     match[i] = S;
 74                     break;
 75                 case 'W':
 76                     match[i] = W;
 77                     break;
 78                 case 'E':
 79                     match[i] = E;
 80                     break;
 81                 }
 82             }
 83             bfs();
 84     }
 85     return 0;
 86 }
 87  
 88 void bfs(){
 89     queue <state> buffer;
 90     buffer.push(state(P_x, P_y, H_x, H_y));
 91  
 92     state temp, next;
 93  
 94     while (!buffer.empty()){
 95         temp = buffer.front();
 96         buffer.pop();
 97         if (temp.step > 255){
 98             cout << "Impossible" << endl;
 99             return;
100         }
101         for (int i = 0; i < 4; i++){
102             next.P_x = temp.P_x + move[i][0];
103             next.P_y = temp.P_y + move[i][1];
104             next.H_x = temp.H_x + move[match[i]][0];
105             next.H_y = temp.H_y + move[match[i]][1];
106             next.step = temp.step + 1;
107          
108             if (next.judge() && _mape[next.H_x][next.H_y] != '!' 
109         && _mape[next.P_x][next.P_y] == '.' ){
110                 if (_mape[next.H_x][next.H_y] == '#'){
111                     next.H_x -= move[match[i]][0];
112                     next.H_y -= move[match[i]][1];
113                 }
114                 if (!visit[next.P_x][next.P_y][next.H_x][next.H_y]){
115                     visit[next.P_x][next.P_y][next.H_x][next.H_y] = true;
116                     if (next.same() || temp.ismeet(next)){
117                         cout << next.step << endl;
118                         return ;
119                     }
120                     else
121                         buffer.push(next);
122                 }
123             }
124         }
125  
126     }
127     cout << "Impossible" << endl;
128 }