题目描述
立体推箱子是一个风靡世界的小游戏。
游戏地图是一个 N 行 M 列的矩阵,每个位置可能是硬地(用 . 表示)、易碎地面(用 E 表示)、禁地(用 # 表示)、起点(用 X 表示)或终点(用 O 表示)。
你的任务是操作一个 1×1×2 的长方体。
这个长方体在地面上有两种放置形式,“立”在地面上(1×1 的面接触地面)或者“躺”在地面上(1×2 的面接触地面)。
在每一步操作中,可以按上下左右四个键之一。
按下按键之后,长方体向对应的方向沿着棱滚动 90 度。
任意时刻,长方体不能有任何部位接触禁地,并且不能立在易碎地面上。
字符 X 标识长方体的起始位置,地图上可能有一个 X 或者两个相邻的 X。
地图上唯一的一个字符 O 标识目标位置。
求把长方体移动到目标位置(即立在 O 上)所需要的最少步数。
在移动过程中,X 和 O 标识的位置都可以看作是硬地被利用。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=506;
struct P {
int x,y; // x, y代表左上部分的坐标
int lie; // lie代表状态 : 0->立起 1->横向 2->纵向
} st, ed;
//搜索状态
char s[N][N]; // 地图
int n, m, d[N][N][3]; // 地图大小 步数
//移动数组常量
const int dx[4] = {0,0,-1,1};
const int dy[4] = {-1,1,0,0};
const int n_x[3][4] = { {0,0,-2,1}, {0,0,-1,1}, {0,0,-1,2} };
const int n_y[3][4] = { {-2,1,0,0}, {-1,2,0,0}, {-1,1,0,0} };
const int n_lie[3][4] = { {1,1,2,2}, {0,0,1,1}, {2,2,0,0} };
// n_w[i][j]表示状态 i 向 j 方向滚动后 w 的变化
queue<P> q;
// bfs队列
bool check_in(int x,int y) {return x>=1 && x<=n && y>=1 && y<=m;}
// 检查是否出界
bool check_lie(P p) {
if (!check_in(p.x,p.y)) return 0; // 出界
if (s[p.x][p.y] == '#') return 0; // 此处为禁区
if (p.lie == 0 && s[p.x][p.y] != '.') return 0; // 无法直立
if (p.lie == 1 && s[p.x][p.y+1] == '#') return 0; // 下半部分不合法
if (p.lie == 2 && s[p.x+1][p.y] == '#') return 0; // 右半部分不合法
return 1; // 可以行动
}
// 检查决策是否合法
int bfs() {
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
for (int k=0; k<3; k++)
d[i][j][k] = -1;
queue<P> empty;
swap(q, empty);
d[st.x][st.y][st.lie] = 0;
q.push(st);
// 预处理
while (q.size()) {
P now = q.front(); q.pop();
for (int i=0; i<4; i++) {
P p;
p.x = now.x + n_x[now.lie][i];
p.y = now.y + n_y[now.lie][i];
p.lie = n_lie[now.lie][i];
//扩展后状态为 p
if (!check_lie(p)) continue;
if (d[p.x][p.y][p.lie] == -1) {
d[p.x][p.y][p.lie] = d[now.x][now.y][now.lie] + 1;
q.push(p);
if (p.x == ed.x && p.y == ed.y && p.lie == ed.lie) // 终点进入合法队列
return d[p.x][p.y][p.lie];
}
}
}
return -1; // 无法到达终点
}
int main() {
while (cin>>n>>m && n) {
for (int i=1; i<=n; i++) // 读入
scanf("%s",s[i]+1);
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
if (s[i][j] == 'O') { // 处理终点状态
ed.x = i;
ed.y = j;
ed.lie = 0;
s[i][j] = '.'; // 此处可移动
}
else if (s[i][j] == 'X') { // 处理起点状态
for (int k=0; k<4; k++) {
int x = i + dx[k],
y = j + dy[k];
if (check_in(x,y) && s[x][y] == 'X') { // 非直立
st.x = min(i, x);
st.y = min(j, y);
st.lie = k < 2 ? 1 : 2;
s[i][j] = s[x][y] = '.';
break;
}
}
if (s[i][j] == 'X') { // 直立
st.x = i;
st.y = j;
st.lie = 0;
}
}
int ans = bfs();
if (ans == -1) puts("Impossible");
else cout<<ans<<endl;
}
return 0;
}