算法题-[Leetcode] 1263 推箱子
题目不难，但是hard级别的……其实之前zoj上有一道类似的题。给定一个地图，行列最大20 * 20，初始状态给定。有几种字符：
（1） 墙 #
(2) 空地.
(3) 箱子B，只在空地上，只有一个。
（4）游戏者S，只在空地上，只有一个。
（5）目的地T, 只在空地上，只有一个。
人可以上下左右走，不能超出地图，也不能走到墙和箱子的位置。人如果和箱子相邻，可以推箱子，箱子会朝人的反方向走一步（如果人在箱子下方，则人只能朝上推箱子）。显然，箱子也不能走进墙。问人把箱子推到目的地，至少推几次？（人不推箱子的行动不计入步数）。如果无解，输出-1。
例如：输入
######
#T####
#..B.#
#.##.#
#...S#
######
输出3。
分析: 只有推才算一步，不过没关系——就是最短路。推荐使用优先队列的最短路实现。
搞清楚几个问题：
（1） 状态：人的位置和箱子的位置。(sx, sy), (bx, by)，根据数据范围，每个坐标可以用5bit，总共20bit，所以用一个int存就好了。
（2）步数：推了几次。
（3）怎么推？ 如果人和箱子相邻——|sx - bx| + |sy - by| == 1，这时推箱子只能朝一个方向推。即(bx - sx, by - sy)的方向。新箱子坐标是bx' = bx * 2 - sx, by' = by * 2 - sy，当然这个位置不能越出地图，也不能是墙。新人的坐标bx' = sx, by' = sy，这个位置一定是合法的，因为是箱子之前的位置。
（4）为了朝别的方向推箱子，人可能自己移动。 这个就是普通的4个方向上、下、左、右移动。注意新的位置，不能是墙或箱子，也不能越界。
（5）优先队列 priority_queue<pair<int, int>> 第一维是步数的相反数——因为是最大值优先，第二维是状态。每个状态，第一次出队时（而不是入队时）是达到这个状态的最小步数。
（6） 复杂度？O(m * n * log(mn))，系数是4左右，因为有4种方式移动，推箱子也是4种移动之一。另外，入队时可以加一个优化——之前出队的状态不重复入队了，不过通常没必要如此（我没加这个）。
代码：
class Solution {public:int minPushBox(vector<vector<char>>& grid) {const int dx[] = {-1, 0, 1, 0};const int dy[] = {0, 1, 0, -1};int m = grid.size(), n = grid[0].size(), state = 0, tx, ty;for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] == 'S') {state |= (i << 5) | j;} else if (grid[i][j] == 'B') {state |= (i << 15) | (j << 10);} else if (grid[i][j] == 'T') {tx = i;ty = j;}}}int dp[20][20][20][20];memset(dp, 0xff, sizeof(dp));priority_queue<pair<int, int>> q;q.push(make_pair(0, state));while (!q.empty()) {int step = -q.top().first;int bx = q.top().second >> 15;int by = (q.top().second >> 10) & 31;int sx = (q.top().second >> 5) & 31;int sy = q.top().second & 31;q.pop();if (dp[bx][by][sx][sy] >= 0) {continue;}if (bx == tx && by == ty) {return step;}dp[bx][by][sx][sy] = step;for (int i = 0; i < 4; ++i) {int xx = sx + dx[i];int yy = sy + dy[i];if (xx >= 0 && xx < m && yy >= 0 && yy < n && grid[xx][yy] != '#' && (xx != bx || yy != by)) {q.push(make_pair(-step, (bx << 15) | (by << 10) | (xx << 5) | yy));}}if (abs(bx - sx) + abs(by - sy) == 1) {int xx = bx, yy = by;bx += bx - sx;by += by - sy;if (bx >= 0 && bx < m && by >= 0 && by < n && grid[bx][by] != '#') {q.push(make_pair(-step - 1, (bx << 15) | (by << 10) | (xx << 5) | yy));}}}return -1;}};
扫描二维码
获取更多精彩
金科优源汇