算法leetcode

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

字数统计: 1.9k字   |   阅读时长: 9分
, ,

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

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的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