原题链接： https://www.acwing.com/problem/content/174/

题目描述

立体推箱子是一个风靡世界的小游戏。 游戏地图是一个N行M列的矩阵，每个位置可能是硬地（用”.”表示）、易碎地面（用”E”表示）、禁地（用”#”表示）、起点（用”X”表示）或终点（用”O”表示）。 你的任务是操作一个1×1×2的长方体。 这个长方体在地面上有两种放置形式，“立”在地面上（1×1的面接触地面）或者“躺”在地面上（1×2的面接触地面）。 在每一步操作中，可以按上下左右四个键之一。 按下按键之后，长方体向对应的方向沿着棱滚动90度。 任意时刻，长方体不能有任何部位接触禁地，并且不能立在易碎地面上。 字符”X”标识长方体的起始位置，地图上可能有一个”X”或者两个相邻的”X”。 地图上唯一的一个字符”O”标识目标位置。 求把长方体移动到目标位置（即立在”O”上）所需要的最少步数。 在移动过程中，”X”和”O”标识的位置都可以看作是硬地被利用。 输入格式 输入包含多组测试用例。 对于每个测试用例，第一行包括两个整数N和M。 接下来N行用来描述地图，每行包括M个字符，每个字符表示一块地面的具体状态。 当输入用例N=0，M=0时，表示输入终止，且该用例无需考虑。 输出格式 每个用例输出一个整数表示所需的最少步数，如果无解则输出”Impossible”。 每个结果占一行。 数据范围 3≤N,M≤500 输入样例： 7 7 ####### #…X### #…##O# #…E# #…E# #…# ####### 0 0 输出样例： 10

题解

1.状态表示：可以知道题中状态不仅有坐标，还有箱子的放法（横躺， 竖躺，直立）。定义一个结构体。 2.状态转移：三个状态变量，开一个三维数组，提前存好各种操作后，状态的偏移量 3.状态计算：因为要求最小步数，可以看成一个边权为1的无向图求最短路，普通BFS即可。

#include <iostream> #include <cstring> #include <algorithm> #include <queue> using namespace std; int n, m; const int N = 510, M = 510; char g[N][M]; int dist[N][N][3]; struct State { int x, y, lie; }; //0 直立 1 横躺 2 竖躺 bool check(int x, int y) { if(x < 0 || x >= n || y < 0 || y >= m) return false; return g[x][y] != '#'; } int bfs(State start, State end) { queue<State> q; memset(dist, -1, sizeof dist); dist[start.x][start.y][start.lie] = 0; q.push(start); int d[3][4][3] = { { {-2, 0, 2}, {0, 1, 1}, {1, 0, 2}, {0, -2, 1} }, //立 上， 右， 下， 左 { {-1, 0, 1}, {0, 2, 0}, {1, 0, 1}, {0, -1, 0} }, //横躺 { {-1, 0, 0}, {0, 1, 2}, {2, 0, 0}, {0, -1, 2} } //竖躺 }; while(q.size()) { auto t = q.front(); q.pop(); for(int i = 0; i < 4; i++) { State next = {t.x + d[t.lie][i][0], t.y + d[t.lie][i][1], d[t.lie][i][2]}; int x = next.x, y = next.y; if(!check(x, y)) continue; if(next.lie == 0) { if(g[x][y] == 'E') { continue; } } else if (next.lie == 1) { if(!check(x, y + 1)) continue; } else { if(!check(x + 1, y)) continue; } if(dist[x][y][next.lie] == -1) { dist[x][y][next.lie] = dist[t.x][t.y][t.lie] + 1; q.push(next); } } } return dist[end.x][end.y][end.lie]; } int main() { while(cin >> n >> m, n || m) { for(int i = 0; i < n; i++) scanf("%s", g[i]); State start = {-1}, end; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) { if(g[i][j] == 'X'&&start.x == -1) { if(g[i+1][j] == 'X') start = {i, j, 2}; else if(g[i][j+1] == 'X') start = {i, j, 1}; else start = {i, j, 0}; } if(g[i][j] == 'O') end = {i, j, 0}; } int res = bfs(start, end); if(res == -1) puts("Impossible"); else printf("%d\n", res); } return 0; }