【搜索难题】力扣1263-推箱子

  |  

摘要: 搜索难题,推箱子问题

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


本文我们看一个很有挑战性的搜索问题,算法的框架是以 BFS 为核心的最短路径。但是有两个难点:

  • 在推 BFS 的过程中,需要维护很复杂的状态,比如表示人的状态、表示箱子的状态等。状态的定义和转移需要仔细设计。
  • 队列也需要做一些改进,有两个方向,一个是双端队列、一个是优先级队列。

经过对状态和转移过程的分析,我们发现每步转移的代价(边权)只有 0 和 1 两种,因此可以用双端队列 BFS 维护复杂状态。

在文章 双端队列 BFS 中我们解决了双端队列 BFS 的问题、在 带压缩的额外状态的 BFS 中我们解决了 BFS 中带着复杂状态压缩的问题,而本题是这两种问题的综合。

同时,本题也可以用优先级队列来做,状态的定义和转移不变。在文章 优先级队列BFS 中我们解决过相关的问题,这里大同小异,只是推 BFS 的过程中持有的状态更加复杂。

$1 题目

「推箱子」是一款风靡全球的益智小游戏,玩家需要将箱子推到仓库中的目标位置。

游戏地图用大小为 n * m 的网格 grid 表示,其中每个元素可以是墙、地板或者是箱子。

现在你将作为玩家参与游戏,按规则将箱子 ‘B’ 移动到目标位置 ‘T’ :

  • 玩家用字符 ‘S’ 表示,只要他在地板上,就可以在网格中向上、下、左、右四个方向移动。
  • 地板用字符 ‘.’ 表示,意味着可以自由行走。
  • 墙用字符 ‘#’ 表示,意味着障碍物,不能通行。
  • 箱子仅有一个,用字符 ‘B’ 表示。相应地,网格上有一个目标位置 ‘T’。
  • 玩家需要站在箱子旁边,然后沿着箱子的方向进行移动,此时箱子会被移动到相邻的地板单元格。记作一次「推动」。
  • 玩家无法越过箱子。

返回将箱子推到目标位置的最小 推动 次数,如果无法做到,请返回 -1。

提示:

1
2
3
4
1 <= grid.length <= 20
1 <= grid[i].length <= 20
grid 仅包含字符 '.', '#',  'S' , 'T', 以及 'B'。
grid 中 'S', 'B' 和 'T' 各只能出现一个。

示例 1:
输入:grid = [[“#”,”#”,”#”,”#”,”#”,”#”],
[“#”,”T”,”#”,”#”,”#”,”#”],
[“#”,”.”,”.”,”B”,”.”,”#”],
[“#”,”.”,”#”,”#”,”.”,”#”],
[“#”,”.”,”.”,”.”,”S”,”#”],
[“#”,”#”,”#”,”#”,”#”,”#”]]
输出:3
解释:我们只需要返回推箱子的次数。

示例 2:
输入:grid = [[“#”,”#”,”#”,”#”,”#”,”#”],
[“#”,”T”,”#”,”#”,”#”,”#”],
[“#”,”.”,”.”,”B”,”.”,”#”],
[“#”,”#”,”#”,”#”,”.”,”#”],
[“#”,”.”,”.”,”.”,”S”,”#”],
[“#”,”#”,”#”,”#”,”#”,”#”]]
输出:-1

示例 3:
输入:grid = [[“#”,”#”,”#”,”#”,”#”,”#”],
[“#”,”T”,”.”,”.”,”#”,”#”],
[“#”,”.”,”#”,”B”,”.”,”#”],
[“#”,”.”,”.”,”.”,”.”,”#”],
[“#”,”.”,”.”,”.”,”S”,”#”],
[“#”,”#”,”#”,”#”,”#”,”#”]]
输出:5
解释:向下、向左、向左、向上再向上。

示例 4:
输入:grid = [[“#”,”#”,”#”,”#”,”#”,”#”,”#”],
[“#”,”S”,”#”,”.”,”B”,”T”,”#”],
[“#”,”#”,”#”,”#”,”#”,”#”,”#”]]
输出:-1

$2 题解

算法1:双端队列 BFS

定义状态

状态比较复杂,由人和箱子共同决定

1
2
3
4
5
6
7
8
9
10
struct State
{
int x, y, bx, by;
int d;
State(int x, int y, int bx, int by, int d):x(x),y(y),bx(bx),by(by),d(d){}
bool operator<(const State& s) const
{
return d > s.d;
}
};

(x, y) 为人的位置,(bx, by) 为箱子的位置,d 为初始状态到当前状态的最短代价

状态转移

状态转移时,枚举人的下一个位置 (x, y),如果 (x, y) 与箱子当前的位置 (cur.bx, cur.by) 是否重叠if(x == cur.bx && y == cur.by)

(1). 重叠

则需要按照方向获得箱子的新位置,压入新状态时,需要将箱子的新位置也给进去,同时代价加1。

1
State(x, y, bx, by, cur.d + 1)

(2). 不重叠

则新状态只更新人的新位置即可,箱子的位置和代价均不变。

1
State(x, y, cur.bx, cur.by, cur.d)

通过以上状态转移的分析,发现每步转移的代价(边权)为 0 或 1,因此可以用双端队列维护这种状态转移。参考 【搜索难题】力扣1368-双端队列BFS

代码 (C++)

双端队列:对 d 有贡献的状态从头进入,对 d 没有贡献的从尾进入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution {
public:
int minPushBox(vector<vector<char>>& grid) {
int n = grid.size(), m = grid[0].size();
// 起始状态
State state(-1, -1, -1, -1, 0);
int ex = -1, ey = -1;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
{
if(grid[i][j] == 'B')
{
state.bx = i;
state.by = j;
}
if(grid[i][j] == 'S')
{
state.x = i;
state.y = j;
}
if(grid[i][j]== 'T')
{
ex = i;
ey = j;
}
}

memset(dist, -1, sizeof(dist));
deque<State> q;
q.push_back(state);
dist[state.x][state.y][state.bx][state.by] = 0;
while(!q.empty())
{
State cur = q.front();
q.pop_front();
if(cur.bx == ex && cur.by == ey)
return dist[cur.x][cur.y][ex][ey];
for(int d = 0; d < 4; ++d)
{
int x = cur.x + dx[d];
int y = cur.y + dy[d];
if(x >= n || x < 0 || y >= m || y < 0)
continue;
if(grid[x][y] == '#')
continue;
if(x == cur.bx && y == cur.by)
{
// 箱子的下一个位置
int bx = cur.bx + dx[d];
int by = cur.by + dy[d];
if(bx < 0 || bx >= n || by < 0 || by >= m)
continue;
if(grid[bx][by] == '#')
continue;
if(dist[x][y][bx][by] == -1 || dist[x][y][bx][by] > cur.d + 1)
{
dist[x][y][bx][by] = cur.d + 1;
q.push_back(State(x, y, bx, by, cur.d + 1));
}
}
else
{
if(dist[x][y][cur.bx][cur.by] == -1 || dist[x][y][cur.bx][cur.by] > cur.d)
{
dist[x][y][cur.bx][cur.by] = cur.d;
q.push_front(State(x, y, cur.bx, cur.by, cur.d));
}
}
}
}
return -1;
}

private:
int dist[21][21][21][21];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
};

算法2: 优先级队列 BFS(dijkstra)

作为对比,将优先级队列 BFS 的做法放在这里。

状态的定义和转移不变,仅仅将双端队列改为优先级队列。排序规则就是按照状态持有的距离 state.d,越小的越早出队。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
struct State
{
int x, y, bx, by;
int d;
State(int x, int y, int bx, int by, int d):x(x),y(y),bx(bx),by(by),d(d){}
bool operator<(const State& s) const
{
return d > s.d;
}
};

class Solution {
public:
int minPushBox(vector<vector<char>>& grid) {
int n = grid.size(), m = grid[0].size();
// 起始状态
State state(-1, -1, -1, -1, 0);
int ex = -1, ey = -1;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
{
if(grid[i][j] == 'B')
{
state.bx = i;
state.by = j;
}
if(grid[i][j] == 'S')
{
state.x = i;
state.y = j;
}
if(grid[i][j]== 'T')
{
ex = i;
ey = j;
}
}

memset(dist, -1, sizeof(dist));
priority_queue<State> pq;
pq.push(state);
dist[state.x][state.y][state.bx][state.by] = 0;
while(!pq.empty())
{
State cur = pq.top();
pq.pop();
if(cur.bx == ex && cur.by == ey)
return dist[cur.x][cur.y][ex][ey];
for(int d = 0; d < 4; ++d)
{
int x = cur.x + dx[d];
int y = cur.y + dy[d];
if(x >= n || x < 0 || y >= m || y < 0)
continue;
if(grid[x][y] == '#')
continue;
if(x == cur.bx && y == cur.by)
{
// 箱子的下一个位置
int bx = cur.bx + dx[d];
int by = cur.by + dy[d];
if(bx < 0 || bx >= n || by < 0 || by >= m)
continue;
if(grid[bx][by] == '#')
continue;
if(dist[x][y][bx][by] == -1 || dist[x][y][bx][by] > cur.d + 1)
{
dist[x][y][bx][by] = cur.d + 1;
pq.push(State(x, y, bx, by, cur.d + 1));
}
}
else
{
if(dist[x][y][cur.bx][cur.by] == -1 || dist[x][y][cur.bx][cur.by] > cur.d)
{
dist[x][y][cur.bx][cur.by] = cur.d;
pq.push(State(x, y, cur.bx, cur.by, cur.d));
}
}
}
}
return -1;
}

private:
int dist[21][21][21][21];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
};

Share