Luobuyu's Blog

0%

1263. 推箱子

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 5.7k 阅读时长 ≈ 5 分钟
推箱子游戏。

1263.推箱子

题目描述：

推箱子游戏。地图大小是 $n \times m$ 的网格 $grid$ ，箱子是 B，目标位置是 T，玩家是 S，空地板是 .，墙是 #。返回将箱子推到目标位置的最小移动步数，如果无法移到目标位置则返回 -1。

数据范围：

$1\le n,m\le 20$

题解：

最小步数需要使用 bfs 来进行求解。

但是需要人来推箱子，如果是箱子自己移动的话就是一个迷宫问题，需要人推箱子的话，人先需要移动到箱子旁边，然后推。可以使用两层 bfs 求解。外层移动箱子，内层人移动到箱子旁边（内层可以求解箱子可以移动的方向，也即是人可以移动到箱子的哪一侧）。外层bfs需要记录人的位置，箱子的位置和最小步数，因为人的位置不同，箱子能够移动的方向可能也会不同。内层bfs求解方向数组，外层枚举遍历的方向即可。使用 $i \times m + j$ 记录状态可以减少维数。

01bfs：

首先这是一个最短路问题，有效移动权重是 $1$ ，非有效移动权重是 $0$ ，就是一个在边权只有 $0$ 和 $1$ 的图上求最短路的问题，可以使用 01bfs 求解，比一般的最短路算法复杂度低。使用 01bfs对人进行移动，如果移动到了箱子的位置那么对箱子进行移动，权重为 $1$ ，加入队列尾部，如果没有移动到箱子的位置则权重为 $0$ ，加入队列头部。需要记录的也是箱子位置，人位置，步数。

代码：

双层bfs

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 4e2 + 10;
    int n, m;
    bool vis[maxn][maxn], vis_play[maxn];
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    bool dir[4];
    struct Node
    {
        int play_pos;
        int box_pos;
        int step;
        Node() {}
        Node(int play_pos, int box_pos, int step) : play_pos(play_pos), box_pos(box_pos), step(step) {}
    };
    int make_pos(pair<int, int> &pos) { return pos.first * m + pos.second; }
    pair<int, int> get_xy(int &pos) { return {pos / m, pos % m}; }
    void bfs_play(int play, int box, vector<vector<char>> &grid)
    {
        queue<int> q;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                vis_play[i * m + j] = false;
        for (int i = 0; i < 4; ++i)
            dir[i] = false;
        q.push(play);
        vis_play[play] = true;
        pair<int, int> box_xy = get_xy(box);
        while (q.size())
        {
            auto out = q.front();
            q.pop();
            pair<int, int> out_xy = get_xy(out);
            if (out_xy.first == box_xy.first + 1 && out_xy.second == box_xy.second)
                dir[0] = true;
            else if (out_xy.first == box_xy.first && out_xy.second == box_xy.second - 1)
                dir[1] = true;
            else if (out_xy.first == box_xy.first - 1 && out_xy.second == box_xy.second)
                dir[2] = true;
            else if (out_xy.first == box_xy.first && out_xy.second == box_xy.second + 1)
                dir[3] = true;
            for (int i = 0; i < 4; ++i)
            {
                int newx = out_xy.first + dx[i];
                int newy = out_xy.second + dy[i];
                if (newx < 0 || newy < 0 || newx >= n || newy >= m || grid[newx][newy] == '#')
                    continue;
                int new_pos = newx * m + newy;
                if (new_pos == box || vis_play[new_pos])
                    continue;
                q.push(new_pos);
                vis_play[new_pos] = true;
            }
        }
    }
    int bfs_box(int play, int start, int end, vector<vector<char>> &grid)
    {
        queue<Node> q;
        vis[play][start] = true;
        q.push(Node(play, start, 0));
        while (q.size())
        {
            auto out = q.front();
            q.pop();
            if (out.box_pos == end)
                return out.step;
            pair<int, int> out_xy = get_xy(out.box_pos);
            bfs_play(out.play_pos, out.box_pos, grid);
            for (int i = 0; i < 4; ++i)
            {
                if (!dir[i])
                    continue;
                int newx = out_xy.first + dx[i];
                int newy = out_xy.second + dy[i];
                if (newx < 0 || newx >= n || newy < 0 || newy >= m || grid[newx][newy] == '#')
                    continue;
                int new_pos = newx * m + newy;
                if (vis[out.box_pos][new_pos])
                    continue;
                q.push(Node(out.box_pos, new_pos, out.step + 1));
                vis[out.box_pos][new_pos] = true;
            }
        }
        return -1;
    }
    int minPushBox(vector<vector<char>> &grid)
    {
        n = grid.size(), m = grid[0].size();
        int start, end, play;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (grid[i][j] == 'S')
                    play = i * m + j;
                else if (grid[i][j] == 'B')
                    start = i * m + j;
                else if (grid[i][j] == 'T')
                    end = i * m + j;
            }
        }
        return bfs_box(play, start, end, grid);
    }
};

01bfs：

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
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 4e2 + 10;
    int n, m;
    bool vis[maxn][maxn];
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    struct Node
    {
        int play_pos;
        int box_pos;
        int step;
        Node() {}
        Node(int play_pos, int box_pos, int step) : play_pos(play_pos), box_pos(box_pos), step(step) {}
    };
    int make_pos(pair<int, int> &pos) { return pos.first * m + pos.second; }
    pair<int, int> get_xy(int &pos) { return {pos / m, pos % m}; }
    int bfs(int play, int start, int end, vector<vector<char>> &grid)
    {
        deque<Node> q;
        q.push_back({play, start, 0});
        vis[play][start] = true;
        while (q.size())
        {
            auto out = q.front();
            q.pop_front();
            if (out.box_pos == end)
                return out.step;
            auto play_pos = get_xy(out.play_pos);
            auto box_pos = get_xy(out.box_pos);
            for (int i = 0; i < 4; ++i)
            {
                pair<int, int> new_play_pos = {play_pos.first + dx[i], play_pos.second + dy[i]};
                if (new_play_pos.first < 0 ||
                    new_play_pos.second < 0 ||
                    new_play_pos.first >= n ||
                    new_play_pos.second >= m ||
                    grid[new_play_pos.first][new_play_pos.second] == '#')
                    continue;
                if (new_play_pos == box_pos)
                {
                    pair<int, int> new_box_pos = {box_pos.first + dx[i], box_pos.second + dy[i]};
                    if (new_box_pos.first < 0 ||
                        new_box_pos.second < 0 ||
                        new_box_pos.first >= n ||
                        new_box_pos.second >= m ||
                        grid[new_box_pos.first][new_box_pos.second] == '#' ||
                        vis[make_pos(new_play_pos)][make_pos(new_box_pos)])
                        continue;
                    q.push_back(Node(make_pos(new_play_pos), make_pos(new_box_pos), out.step + 1));
                    vis[make_pos(new_play_pos)][make_pos(new_box_pos)] = true;
                }
                else
                {
                    if (vis[make_pos(new_play_pos)][out.box_pos])
                        continue;
                    q.push_front(Node(make_pos(new_play_pos), out.box_pos, out.step));
                    vis[make_pos(new_play_pos)][out.box_pos] = true;
                }
            }
        }
        return -1;
    }
    int minPushBox(vector<vector<char>> &grid)
    {
        n = grid.size(), m = grid[0].size();
        int start, end, play;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (grid[i][j] == 'S')
                    play = i * m + j;
                else if (grid[i][j] == 'B')
                    start = i * m + j;
                else if (grid[i][j] == 'T')
                    end = i * m + j;
            }
        }
        return bfs(play, start, end, grid);
    }
};