链接：
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1325
题意：
从迷宫的S处出发，每次可以往东、南、西、北4个方向之一前进。如果前方有墙壁，游戏者可以把墙壁往前推一格。
如果有两堵或者多堵连续的墙，则不能推动。另外，游戏者也不能推动游戏区域边界上的墙。
用最少的步数走出迷宫（边界处没有墙的地方就是出口）。迷宫总是有4行6列，多解时任意输出一个移动序列即可。
分析：
广搜 + 状态压缩。
因为总墙数只有58，所以可以用一个long long型变量来储存一个状态。
用set来判重。
具体实现见代码。
代码：
#include <cstdio>
#include <queue>
#include <set>
using namespace std; typedef long long int LLI;
const int dr[] = {-, , , }; //上下左右
const int dc[] = {, , -, };
const char dir[+] = "NSWE"; struct NODE {
int r, c, f, pre; //所在行，所在列，父方向，父结点
char d; //移动方向
LLI state; //当前状态
} node[]; int wall[][][]; //wall[r][c][d] : 第r行第c列d方向的墙的编号 void constant(){
/* 给墙编号时墙的储存方式：
_ _ _
|_|_|_|
|_|_|_|
|_|_|_|
*/
const int cdr[] = {-, , , }; //上下左右
const int cdc[] = {, , -, };
int id = , code[+][+];
for(int c = ; c < ; c += ) code[][c] = id++; //给每一堵墙编号
for(int r = ; r < ; r++){
for(int c = ; c < ; c++) code[r][c] = id++;
}
for(int r = ; r < ; r++){ //获取wall数组
for(int c = ; c < ; c += ){
int t = r - , i = (c - ) / ;
for(int d = ; d < ; d++){
int fr = r + cdr[d], fc = c + cdc[d];
wall[t][i][d] = code[fr][fc];
}
}
}
} void output(int n){ //输出路径
if(node[n].pre) output(node[n].pre);
printf("%c", node[n].d);
} void bfs(){
node[].f = -;
set<LLI> S[][];
S[node[].r][node[].c].insert(node[].state);
queue<int> Q;
Q.push();
int np = ;
while(Q.size()){
int f = Q.front(); Q.pop();
int r = node[f].r;
int c = node[f].c;
LLI& s = node[f].state;
for(int d = ; d < ; d++){
if(d == node[f].f) continue; //避免向父方向返回
LLI state = s;
bool valid = true;
int fr = r + dr[d], fc = c + dc[d];
if(state & 1LL << wall[r][c][d]){ //若前面有墙
if(fr < || fr > || fc < || fc > ) valid = false; //超出边界
else if(state & 1LL << wall[fr][fc][d]) valid = false; //多堵墙连续
else{ //移动该墙
state |= 1LL << wall[fr][fc][d];
state ^= 1LL << wall[r][c][d];
}
}
if(!valid) continue;
if(fr < || fr > || fc < || fc > ){ //找到出口
node[np].d = dir[d];
node[np].pre = f;
output(np);
printf("\n");
return;
}
if(S[fr][fc].count(state)) continue;
S[fr][fc].insert(state);
node[np].r = fr;
node[np].c = fc;
node[np].f = d ^ ; //d的相反方向
node[np].d = dir[d];
node[np].pre = f;
node[np].state = state;
Q.push(np++);
}
}
} int main(){
constant();
const int wei[] = {, , , };
while(scanf("%d%d", &node[].c, &node[].r) && node[].r){
node[].r--; node[].c--; node[].state = ;
for(int r = ; r < ; r++){
for(int c = ; c < ; c++){
int n;
scanf("%d", &n);
for(int d = ; d < ; d++){ //判断上下左右是否有墙
if(n & wei[d]) node[].state |= 1LL << wall[r][c][d];
}
}
}
bfs();
}
return ;
}