UVA 589 - Pushing Boxes（BFS+状态判重）搜索-广度优先搜索

题目链接：589 - Pushing Boxes
题意：就是模拟推箱子游戏，要求推箱子次数最少，然后是总次数最少的方案。
思路：广搜+状态判重，用人的位置和箱子位置和当前步数作为状态。然后由于是要优先推箱子次数少，所以利用优先队列去取状态。
代码：

#include #include #include #include #include #include #include #define INF 0x3f3f3f3f using namespace std; const int d[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; const char s1[10] = "NSEW"; const char s2[10] = "nsew"; const int N = 25; int r, c, push_num; char g[N][N]; string ans; map vis[20][20][20][20]; typedef pair pi; pi s, b, t; struct State { int sx, sy, bx, by, num; string path; State() {} State(int _sx, int _sy, int _bx, int _by, int _num) { sx = _sx; sy = _sy; bx = _bx; by = _by; num = _num; path = ""; } friend bool operator < (State a, State b) { if (a.num != b.num) return a.num > b.num; return a.path.length() > b.path.length(); } }; void init() { ans = ""; push_num = INF; for (int i = 0; i < r; i++) { scanf("%s", g[i]); for (int j = 0; j < c; j++) { if (g[i][j] == 'S') s = make_pair(i, j); else if (g[i][j] == 'B') b = make_pair(i, j); else if (g[i][j] == 'T') t = make_pair(i, j); if (g[i][j] != '#') g[i][j] = '.'; for (int k = 0; k < r; k++) for (int l = 0; l < c; l++) vis[i][j][k][l].clear(); } } }bool check(int x, int y) { if (x < 0 || x >= r || y < 0 || y >= c || g[x][y] != '.') return false; return true; }void solve() { priority_queue Q; vis[s.first][s.second][b.first][b.second][0] = 1; Q.push(State(s.first, s.second, b.first, b.second, 0)); while (!Q.empty()) { State p = Q.top(); Q.pop(); if (p.bx == t.first && p.by == t.second) { if (push_num > p.num) { ans = p.path; push_num = p.num; } else if (push_num == p.num) { if (ans.length() > p.path.length()) ans = p.path; } else break; continue; } for (int i = 0; i < 4; i++) { State q = p; q.sx += d[i][0]; q.sy += d[i][1]; if (!check(q.sx, q.sy)) continue; q.path += s2[i]; if (q.sx == q.bx && q.sy == q.by) { q.bx += d[i][0], q.by += d[i][1]; if (!check(q.bx, q.by)) continue; q.num++; if (q.num > push_num) continue; q.path[q.path.length() - 1] = s1[i]; } if (vis[q.sx][q.sy][q.bx][q.by][ans.length()]) continue; vis[q.sx][q.sy][q.bx][q.by][ans.length()] = true; Q.push(q); } } }int main() { int cas = 0; while (~scanf("%d%d", &r, &c) && r || c) { init(); printf("Maze #%d\n", ++cas); solve(); if (ans.length()) cout << ans << endl; else printf("Impossible.\n"); printf("\n"); } return 0; }

【UVA 589 - Pushing Boxes（BFS+状态判重）】