1263-推箱子(Minimum Moves to Move a Box to Their Target Location)
发表于：2021-12-03 | 分类： 困难
字数统计: 2.6k | 阅读时长: 12分钟 | 阅读量：

原文链接: https://leetcode-cn.com/problems/minimum-moves-to-move-a-box-to-their-target-location

英文原文

A storekeeper is a game in which the player pushes boxes around in a warehouse trying to get them to target locations.

The game is represented by an m x n grid of characters grid where each element is a wall, floor, or box.

Your task is to move the box 'B' to the target position 'T' under the following rules:

  • The character 'S' represents the player. The player can move up, down, left, right in grid if it is a floor (empty cell).
  • The character '.' represents the floor which means a free cell to walk.
  • The character '#' represents the wall which means an obstacle (impossible to walk there).
  • There is only one box 'B' and one target cell 'T' in the grid.
  • The box can be moved to an adjacent free cell by standing next to the box and then moving in the direction of the box. This is a push.
  • The player cannot walk through the box.

Return the minimum number of pushes to move the box to the target. If there is no way to reach the target, return -1.

 

Example 1:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#",".","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 3
Explanation: We return only the number of times the box is pushed.

Example 2:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#","#","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: -1

Example 3:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T",".",".","#","#"],
               ["#",".","#","B",".","#"],
               ["#",".",".",".",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 5
Explanation:  push the box down, left, left, up and up.

Example 4:

Input: grid = [["#","#","#","#","#","#","#"],
               ["#","S","#",".","B","T","#"],
               ["#","#","#","#","#","#","#"]]
Output: -1

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 20
  • grid contains only characters '.', '#', 'S', 'T', or 'B'.
  • There is only one character 'S', 'B', and 'T' in the grid.

中文题目

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

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

现在你将作为玩家参与游戏，按规则将箱子 'B' 移动到目标位置 'T' ：

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

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

 

示例 1：

输入：grid = [["#","#","#","#","#","#"],
             ["#","T","#","#","#","#"],
             ["#",".",".","B",".","#"],
             ["#",".","#","#",".","#"],
             ["#",".",".",".","S","#"],
             ["#","#","#","#","#","#"]]
输出：3
解释：我们只需要返回推箱子的次数。

示例 2：

输入：grid = [["#","#","#","#","#","#"],
             ["#","T","#","#","#","#"],
             ["#",".",".","B",".","#"],
             ["#","#","#","#",".","#"],
             ["#",".",".",".","S","#"],
             ["#","#","#","#","#","#"]]
输出：-1

示例 3：

输入：grid = [["#","#","#","#","#","#"],
             ["#","T",".",".","#","#"],
             ["#",".","#","B",".","#"],
             ["#",".",".",".",".","#"],
             ["#",".",".",".","S","#"],
             ["#","#","#","#","#","#"]]
输出：5
解释：向下、向左、向左、向上再向上。

示例 4：

输入：grid = [["#","#","#","#","#","#","#"],
             ["#","S","#",".","B","T","#"],
             ["#","#","#","#","#","#","#"]]
输出：-1

 

提示：

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

通过代码

高赞题解

BFS：

  1. BFS 每走一步，会把下一步能走的格子加入队列
  2. 按顺序走完这一步所有的可能，队列里就剩下下一步所有的可能
  3. 当走到终点时，就是最少步骤
  4. 每走一步，还会使用 set 来记录已经走到过的格子的坐标
  5. 把下一步加入队列前，检查，重复的就不用进队列了

分析：

  1. 如果这道题没有人，箱子自己走，那么只需要了解BFS，就可以解决了
  2. 如果有人存在，把人的状态同时记录下来
  3. 当人走到箱子的格子上，把箱子沿同一方向移动，如果箱子位置合法，那就是推动箱子了

问题和解决：

同时记录人和箱子的状态，会有一些问题要解决

  1. 因为人也动，箱子也动，但是只有箱子动才算步数，所以加入队列的顺序，并不是步数顺序了
    所以需要一个记录步数，同时记录人和箱子的坐标，还可以排序的队列
    使用 priority_queue（优先队列）解决。
    []
    priority_queue<vector<size_t>, vector<vector<size_t>>, greater<vector<size_t>>> pq;
    队列中的数据是 vector<size_t>
    优先队列会使用 vector<vector<size_t>> 来保存 vector<size_t>
    设置为升序存储 greater<vector<size_t>>

    其中 vector<size_t> 保存的内容是：
    [0] 当前状态最小推箱子次数
    [1] 人的坐标 x
    [2] 人的坐标 y
    [3] 箱子的坐标 x
    [4] 箱子的坐标 y

  2. set 怎么调整
    set<vector<size_t>> 用人和箱子的坐标来做记录

    [0] 人的坐标 x
    [1] 人的坐标 y
    [2] 箱子的坐标 x
    [3] 箱子的坐标 y

解题思路：

  1. 定义优先队列
  2. 将原始数据中的人和箱子坐标提取出来，地图还原成通路
  3. 将起始状态存入队列
  4. 定义 set
  5. 将起始状态存入 set
  6. 定义方向数组
  7. 开始 bfs 吧，while (!pq.empty())
  8. 对人移动，检查合法性
  9. 检查人是否走到箱子上
    1. 移动箱子，检查合法性
    2. 步数 +1
  10. 判断箱子是否到终点，返回步数
  11. 检查 set，移动后是否重复，记录 set
  12. 如果 bfs 没结果，无法到达终点，返回 -1

模拟：

<1.png,2.png,3.png,4.png,5.png>

做了几张图帮助理解一下，虽然只有开始的几步，但是如果理解了，后面脑补就可以了。

可以看到，当从队列中取出一个状态，4 种情况有一种情况是推动箱子，另一种是箱子没动人动。
当 4 种情况中合理的都加入队列后，根据优先队列的排序，下一个状态是优先箱子没动人动的情况。
因为题目的最终目的是求最少的箱子移动步数，所以只要箱子没动，步数都不增加，那么优先级就会高
所以 bfs 才能按照步数作为参考

答题

[]
int minPushBox(vector<vector<char>>& grid) 
{
	// pq，[0]当前状态最小推箱子次数 [1]人的坐标x [2]人的坐标y [3]箱子的坐标x [4]箱子的坐标y
	priority_queue<vector<size_t>, vector<vector<size_t>>, greater<vector<size_t>>> pq;
	size_t m = grid.size();
	size_t n = grid[0].size();

	vector<size_t> a(5, 0);
	for (size_t x = 0; x < m; x++)
	{
		for (size_t y = 0; y < n; y++)
		{
			if (grid[x][y] == 'S')
			{
				a[1] = x;
				a[2] = y;
				grid[x][y] = '.';
			}
			else if (grid[x][y] == 'B')
			{
				a[3] = x;
				a[4] = y;
				grid[x][y] = '.';
			}
		}
	}
	pq.push(a);

	set<vector<size_t>> dist;
	dist.insert({ a[1], a[2], a[3], a[4] });
	int dx[4] = { 0,0,1,-1 };
	int dy[4] = { 1,-1,0,0 };

	while (!pq.empty())
	{
		auto v = pq.top();
		pq.pop();

		for (int i = 0; i < 4; i++)
		{
			vector<size_t> next_s = { v[1] + dx[i], v[2] + dy[i] };
			if (next_s[0] >= m || next_s[1] >= n || grid[next_s[0]][next_s[1]] == '#')
			{
				continue;
			}
			vector<size_t> next_b = { v[3], v[4] };
			size_t d = v[0];
			if (next_s == next_b)
			{
				next_b[0] += dx[i];
				next_b[1] += dy[i];
				if (next_b[0] >= m || next_b[1] >= n || grid[next_b[0]][next_b[1]] == '#')
				{
					continue;
				}
				d++;
			}
			if (grid[next_b[0]][next_b[1]] == 'T')
			{
				return (int)d;
			}

			if (dist.find({next_s[0], next_s[1], next_b[0], next_b[1]}) != dist.end())
			{
				continue;
			}
			dist.insert({ next_s[0], next_s[1], next_b[0], next_b[1] });
			pq.push({ d, next_s[0], next_s[1], next_b[0], next_b[1] });
		}
	}
	return -1;
}

致谢：

感谢 小白二号 @scut_dell 的竞赛题解，让我学到了这种解法。
我学会之后，再详细的讲解，分享给他人。

感谢您的观看，希望对您有帮助，欢迎热烈的交流！

统计信息

通过次数 提交次数 AC比率
3453 8047 42.9%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言
数组 广度优先搜索 矩阵 堆（优先队列）
上一篇:
1262-可被三整除的最大和(Greatest Sum Divisible by Three)
下一篇:
1266-访问所有点的最小时间(Minimum Time Visiting All Points)
本文目录
本文目录
    •
    本站总访问量： 次 |
    Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo