POJ3322 Bloxorz “迷宫”类经典例题

题目大意

游戏地图是一个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”。
每个结果占一行。

样例

输入样例：
7 7
#######
#..X###
#..##O#
#....E#
#....E#
#.....#
#######
0 0
输出样例：
10

思路
       形如给定一个矩形地图， 控制一个物体在地图中按要求移动，求 “最少步数” 的问题。广度优先搜索很擅长解决这种问题一一地图的整体形态是固定不变的，只有少数个体或特征随着每一步操作发生改变。我们只需要把这些变化的部分提取为状态，把起始状态加入队列，使用广度优先搜索不断取出队头状态，沿着分支扩展、入队即可。广度优先搜索是逐层遍历搜索树的算法，所有状态按照入队的先后顺序具有层次单调性(也就是步数单调性)。如果每一次扩展恰好对应一步，那么当一个状态第一次被访问 (入队)时，就得到了从起始状态到达该状态的最少步数。

       在这道题目中，不变的是整个地图，变化的部分有长方体的位置和放置形态。我们可以用一个三元组(x,y,lie) 代表一 个状态(搜索树中的一个节点)，其中lie=0表示长方体立在(x,y); lie=1 表示长方体横向躺着，左半部分位置在(x,y): lie=2表示长方体纵向躺着，上半部分在(x,y), 并用数组d[x][v][lie] 记录从起始状态到达每个状态的最少步数。然后执行广度优先搜索即可。为了程序实现方便，我们用数字0~3分别代指左、右、上、下四个方向。

状态 0 立着

状态 1 横着

状态 2 竖着

用数组来表示4个方向 左 右 上 下 运动后 x, y, lie 的变化

int next_x[3][4] = {{0, 0, -2, 1}, {0, 0, -1, 1}, {0, 0, -1, 2}};
int next_y[3][4] = {{-2, 1, 0, 0}, {-1, 2, 0, 0}, {-1, 1, 0, 0}};
int next_lie[3][4] = {{1, 1, 2, 2}, {0, 0, 1, 1}, {2, 2, 0, 0}};

用next代表下一个状态，表示为

next.x = now.x + next_x[now.lie][i];
next.y = now.y + next_y[now.lie][i];
next.lie = next_lie[now.lie][i];

用get_se()函数得到初始的起点和起点状态，和终点

void get_se(){

}

用valid函数判断下一个状态的合法性

//判断点是否越界
bool valid(int x, int y){
	return x >= 0 && y >= 0 && x < n && y < m;
}
//判断下一个状态是否合理
bool valid(state next){
	if(!valid(next.x, next.y)) return false;
	if(s[next.x][next.y] == '#') return false;
	if(next.lie == 0 && s[next.x][next.y] != '.') return false;
	if(next.lie == 1 && s[next.x][next.y + 1] == '#') return false;
	if(next.lie == 2 && s[next.x + 1][next.y] == '#') return false;
	return true;
}

完整代码

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 510; 
struct state{
	int x, y; //坐标 
	int lie; // 状态 
};
char s[N][N];
state st, ed;
int n, m;
int dis[N][N][3]; //记录最小步数 
queue<state> q;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
bool valid(int x, int y){
	return x >= 0 && y >= 0 && x < n && y < m;
}
bool valid(state next){
	if(!valid(next.x, next.y)) return false;
	if(s[next.x][next.y] == '#') return false;
	if(next.lie == 0 && s[next.x][next.y] != '.') return false;
	if(next.lie == 1 && s[next.x][next.y + 1] == '#') return false;
	if(next.lie == 2 && s[next.x + 1][next.y] == '#') return false;
	return true;
}
void get_se(){
	for (int i = 0; i < n ; i++){
		for(int j = 0; 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];
					int y = j + dy[k];
					if(valid(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 next_x[3][4] = {{0, 0, -2, 1}, {0, 0, -1, 1}, {0, 0, -1, 2}};
int next_y[3][4] = {{-2, 1, 0, 0}, {-1, 2, 0, 0}, {-1, 1, 0, 0}};
int next_lie[3][4] = {{1, 1, 2, 2}, {0, 0, 1, 1}, {2, 2, 0, 0}};
int bfs(){
	memset(dis, -1, sizeof dis);
	while(q.size()) q.pop();
	dis[st.x][st.y][st.lie] = 0;
	q.push(st);
	while(q.size()){
		state now = q.front();
		q.pop();
		for(int i = 0; i < 4; i++){
			state next;
			next.x = now.x + next_x[now.lie][i];
			next.y = now.y + next_y[now.lie][i];
			next.lie = next_lie[now.lie][i];
			if(!valid(next)) continue;
			if(dis[next.x][next.y][next.lie] == -1){
				dis[next.x][next.y][next.lie] = dis[now.x][now.y][now.lie] + 1;
				q.push(next);
				if(next.x == ed.x && next.y == ed.y && next.lie == ed.lie)
					return dis[next.x][next.y][next.lie];
			}
		}
	}
	return -1;
}

int main(){
	while(~scanf("%d%d", &n, &m) && n){
		for(int i = 0; i < n; i++)
		scanf("%s", s[i]); 
		get_se();
		int ans = bfs();
		if(ans == -1)
			cout << "Impossible" << endl;
		else cout << ans << endl;
	}	
	return 0;
}