UVa 10384

链接：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1325

题意：

从迷宫的S处出发，每次可以往东、南、西、北4个方向之一前进。如果前方有墙壁，游戏者可以把墙壁往前推一格。
如果有两堵或者多堵连续的墙，则不能推动。另外，游戏者也不能推动游戏区域边界上的墙。
用最少的步数走出迷宫（边界处没有墙的地方就是出口）。迷宫总是有4行6列，多解时任意输出一个移动序列即可。

分析：

广搜 + 状态压缩。
因为总墙数只有58，所以可以用一个long long型变量来储存一个状态。
用set来判重。
具体实现见代码。

代码：

  1 #include <cstdio>
  2 #include <queue>
  3 #include <set>
  4 using namespace std;
  5 
  6 typedef long long int LLI;
  7 const int dr[4] = {-1, 1, 0, 0}; //上下左右
  8 const int dc[4] = {0, 0, -1, 1};
  9 const char dir[4+5] = "NSWE";
 10 
 11 struct NODE {
 12     int r, c, f, pre; //所在行，所在列，父方向，父结点
 13     char d; //移动方向
 14     LLI state; //当前状态
 15 } node[1000000];
 16 
 17 int wall[4][6][4]; //wall[r][c][d] : 第r行第c列d方向的墙的编号
 18 
 19 void constant(){
 20 /* 给墙编号时墙的储存方式：
 21      _ _ _
 22     |_|_|_|
 23     |_|_|_|
 24     |_|_|_|
 25 */
 26     const int cdr[4] = {-1, 0, 0, 0}; //上下左右
 27     const int cdc[4] = {0, 0, -1, 1};
 28     int id = 0, code[5+5][13+5];
 29     for(int c = 1; c < 12; c += 2) code[0][c] = id++; //给每一堵墙编号
 30     for(int r = 1; r < 5; r++){
 31         for(int c = 0; c < 13; c++) code[r][c] = id++;
 32     }
 33     for(int r = 1; r < 5; r++){ //获取wall数组
 34         for(int c = 1; c < 12; c += 2){
 35             int t = r - 1, i = (c - 1) / 2;
 36             for(int d = 0; d < 4; d++){
 37                 int fr = r + cdr[d], fc = c + cdc[d];
 38                 wall[t][i][d] = code[fr][fc];
 39             }
 40         }
 41     }
 42 }
 43 
 44 void output(int n){ //输出路径
 45     if(node[n].pre) output(node[n].pre);
 46     printf("%c", node[n].d);
 47 }
 48 
 49 void bfs(){
 50     node[0].f = -1;
 51     set<LLI> S[4][6];
 52     S[node[0].r][node[0].c].insert(node[0].state);
 53     queue<int> Q;
 54     Q.push(0);
 55     int np = 1;
 56     while(Q.size()){
 57         int f = Q.front();  Q.pop();
 58         int r = node[f].r;
 59         int c = node[f].c;
 60         LLI& s = node[f].state;
 61         for(int d = 0; d < 4; d++){
 62             if(d == node[f].f) continue; //避免向父方向返回
 63             LLI state = s;
 64             bool valid = true;
 65             int fr = r + dr[d], fc = c + dc[d];
 66             if(state & 1LL << wall[r][c][d]){ //若前面有墙
 67                 if(fr < 0 || fr > 3 || fc < 0 || fc > 5) valid = false; //超出边界
 68                 else if(state & 1LL << wall[fr][fc][d]) valid = false; //多堵墙连续
 69                 else{ //移动该墙
 70                     state |= 1LL << wall[fr][fc][d];
 71                     state ^= 1LL << wall[r][c][d];
 72                 }
 73             }
 74             if(!valid) continue;
 75             if(fr < 0 || fr > 3 || fc < 0 || fc > 5){ //找到出口
 76                 node[np].d = dir[d];
 77                 node[np].pre = f;
 78                 output(np);
 79                 printf("
");
 80                 return;
 81             }
 82             if(S[fr][fc].count(state)) continue;
 83             S[fr][fc].insert(state);
 84             node[np].r = fr;
 85             node[np].c = fc;
 86             node[np].f = d ^ 1; //d的相反方向
 87             node[np].d = dir[d];
 88             node[np].pre = f;
 89             node[np].state = state;
 90             Q.push(np++);
 91         }
 92     }
 93 }
 94 
 95 int main(){
 96     constant();
 97     const int wei[4] = {2, 8, 1, 4};
 98     while(scanf("%d%d", &node[0].c, &node[0].r) && node[0].r){
 99         node[0].r--;  node[0].c--;  node[0].state = 0;
100         for(int r = 0; r < 4; r++){
101             for(int c = 0; c < 6; c++){
102                 int n;
103                 scanf("%d", &n);
104                 for(int d = 0; d < 4; d++){ //判断上下左右是否有墙
105                     if(n & wei[d]) node[0].state |= 1LL << wall[r][c][d];
106                 }
107             }
108         }
109         bfs();
110     }
111     return 0;
112 }