uva 589 - Pushing Boxes(双重bfs）

题目链接：uva 589 - Pushing Boxes

题目大意：推箱子游戏，工人移动用小写，推动箱子用大写，给出推动箱子最少的方法，不用字典序。

解题思路：这题写了一天，一开始考虑到直接bfs，记录箱子和工人的位置以及推动箱子的次数作为状态，结果写好后超时，才发现如果不加推动箱子的次数的话，会将大部分情况合并，时间会减少很多，但是第4组样例会过不了（考虑总步数最少的情况，题目要求推动箱子的次数最少）。

超时代码

#include <stdio.h>
#include <string.h>
#include <set>
#include <queue>

using namespace std;

const int N = 30;
const int d[4][2] = { {0, 1}, {1, 0}, {-1, 0}, {0, -1}};
const char sign[N] = "esnwESNW";

struct point {
	int x, y;
	friend bool operator < (const point& a, const point& b) {
		if (a.x != b.x) return a.x < b.x;
		return a.y < b.y;
	}
	friend bool operator == (const point& a, const point& b) {
		return a.x == b.x && a.y == b.y;
	}
};

struct state {
	int cnt;
	point you, blo;
	queue<int> path;
	friend bool operator < (const state& a, const state& b) {
		if (a.cnt != b.cnt) return a.cnt < b.cnt;
		if (a.you == b.you) return a.blo < b.blo;
		return a.you < b.you;
	}
};

int r, c;
char g[N][N];
state s;
set<state> v;

void init() {
	int flag = 0;
	s.cnt = 0;
	v.clear();
	while (!s.path.empty()) s.path.pop();

	for (int i = 0; i < r; i++) gets(g[i]);

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (g[i][j] == 'S') {
				s.you.x = i; s.you.y = j;
				flag++;
			} else if (g[i][j] == 'B') {
				s.blo.x = i; s.blo.y = j;
				flag++;
			}
			if (flag == 2) break;
		}
	}
}

bool bfs() {
	set<state>::iterator it;
	queue<state> que;	
	que.push(s);
	bool flag = true;
	state u, k, ans;
	ans.cnt = N * N;

	while (!que.empty()) {
		u = que.front(); que.pop();
		
		for (int i = 0; i < 4; i++) {
			k = u;
			k.you.x = u.you.x + d[i][0];
			k.you.y = u.you.y + d[i][1];

			if (k.cnt >= ans. cnt) continue;
			if (k.you == u.blo) {
				k.blo.x = u.blo.x + d[i][0];
				k.blo.y = u.blo.y + d[i][1];
				if (k.blo.x < 0 || k.blo.x >= r || k.blo.y < 0 || k.blo.y >= c) continue;
				if (g[k.blo.x][k.blo.y] == '#') continue;
				k.path.push(i+4);
				k.cnt = u.cnt + 1;

				it = v.find(k);
				if (g[k.blo.x][k.blo.y] == 'T') {
					if (k.cnt < ans.cnt) {
						ans = k; flag = false;
					}
				} else if (it == v.end()) {
					v.insert(k);
					que.push(k);
				}

			} else {
				if (k.you.x < 0 || k.you.x >= r || k.you.y < 0 || k.you.y >= c) continue;
				if (g[k.you.x][k.you.y] == '#') continue;
				k.path.push(i);

				it = v.find(k);
				if (it == v.end()) {
					v.insert(k);
					que.push(k);
				}
			}
		}
	}
	if (!flag) {
		while (!ans.path.empty()) {
			printf("%c", sign[ans.path.front()]);
			ans.path.pop();
		}
		printf("\n");
	}
	return flag;
}

int main() {
	int cas = 1;
	while (scanf("%d%d%*c", &r, &c), r + c) {
		init();
		printf("Maze #%d\n", cas++);
		if (bfs()) printf("Impossible.\n");
		printf("\n");
	}
	return 0;
}

后来想到，BFS就是用来解决步数最少的问题，那我直接对木块的移动进行BFS，每找到一条路就进行判断，看工人是否可以按照木块的移动来推箱子（即能否移动到箱子移动的反方向一格又是一层bfs）。写好后试了一下全空的20*20，结果超时了，因为bfs会将所有可能全部考虑，但是又不能说只找一条（因为这条可能不行），用dfs的话又不能保证最短，还是要全部情况考虑。所以我想了一个优化，对于每个位置，记录移动到的最短步数，大于这个步数的话就不再考虑。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>

using namespace std;

const int N = 30;
const int M = 10000;
const int INF = 0x3f3f3f3f;
const int d[4][2] = { {0, 1}, {1, 0}, {-1, 0}, {0, -1}};
const char sign[N] = "esnwESNW";

struct point {
	int x, y;
};

struct state {
	int x, y;
	int cnt;
	vector<int> rec;
	void clear() {
		x = y = -1;
		cnt = 0;
		rec.clear();
	}
};

int r, c;
state s, b;
char g[N][N];

void init() {
	int flag = 0;
	s.clear();
	b.clear();

	for (int i = 0; i < r; i++) gets(g[i]);

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (g[i][j] == 'S') {
				s.x = i, s.y = j;
				flag++;
			} else if (g[i][j] == 'B') {
				b.x = i, b.y = j;
				flag++;
			}
			if (flag == 2) break;
		}
	}
}

bool bfs(point p, point q, point e, int* ans) {
	queue<point> que;
	point u, k;
	int G[N][N]; memset(G, -1, sizeof(G));
	int vis[M]; memset(vis, 0, sizeof(vis));
	que.push(p);

	while (!que.empty()) {
		u = que.front(); que.pop();
		if (u.x == e.x && u.y == e.y) {
			int xi = u.x, yi = u.y;
			while (G[xi][yi] != -1) {
				int& dir = G[xi][yi];
				vis[++vis[0]] = dir;
				xi += d[3-dir][0]; yi += d[3-dir][1];
			}

			for (int i = vis[0]; i; i--) ans[++ans[0]] = vis[i];
			return false;
		}

		for (int i = 0; i < 4; i++) {
			k.x = u.x + d[i][0]; k.y = u.y + d[i][1];
			if (k.x < 0 || k.x >= r || k.y < 0 || k.y >= c) continue;
			if ((k.x == q.x && k.y == q.y) || (k.x == p.x && k.y == p.y)) continue;
			if (g[k.x][k.y] == '#' || G[k.x][k.y] != -1) continue;

			G[k.x][k.y] = i;
			que.push(k);
		}
	}
	return true;
}

bool judge(state k) {
	int ans[M];
	memset(ans, 0, sizeof(ans));
	int n = k.rec.size();
	point p, q, aid;
	p.x = s.x; p.y = s.y;
	q.x = b.x; q.y = b.y;

	for (int i = 0; i < n; i++) {
		int dir = k.rec[i];
		aid.x = q.x + d[3-dir][0]; aid.y = q.y + d[3-dir][1];
		if (bfs(p, q, aid, ans)) return false;
		ans[++ans[0]] = dir + 4;
		p = q;
		q.x += d[dir][0]; q.y += d[dir][1];
	}

	for (int i = 1; i <= ans[0]; i++) printf("%c", sign[ans[i]]);
	printf("\n");
	return true;
}

bool solve() {
	queue<state> que;
	state u, k;
	que.push(b);
	int v[N][N]; memset(v, INF, sizeof(v));

	while (!que.empty()) {
		u = que.front(); que.pop();

		for (int i = 0; i < 4; i++) {
			int p = u.x + d[3-i][0], q = u.y + d[3-i][1];
			if (p < 0 || p >= r || q < 0 || q >= c || g[p][q] == '#') continue;

			k = u;
			k.x += d[i][0]; k.y += d[i][1];
			if (k.x < 0 || k.x >= r || k.y < 0 || k.y >= c || g[k.x][k.y] == '#') continue;

			if (g[k.x][k.y] == 'T') {
				k.rec.push_back(i);
				if (judge(k)) return false;
			} else {
				k.cnt++;
				if (k.cnt >= v[k.x][k.y]) continue;
				v[k.x][k.y] = k.cnt;
				k.rec.push_back(i);
				que.push(k);
			}
		}
	}
	return true;
}

int main() {
	int cas = 1;
	while (scanf("%d%d%*c", &r, &c), r + c) {
		init();
		printf("Maze #%d\n", cas++);
		if (solve()) printf("Impossible.\n");
		printf("\n");
	}
	return 0;
}