难度困难

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

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

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

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

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

示例 1：

![img](/images/ move-a-box.png)

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

输出：3

解释：我们只需要返回推箱子的次数。

示例 2：

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

输出：-1

示例 3：

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

输出：5

解释：向下、向左、向左、向上再向上。

提示：

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

# BFS + DFS

BFS ，获取当前箱子位置相邻点 cx , cy , px , py

判断人所在位置 px , py 到箱子相邻点的对称点 sx , sy 是否可达

可达，则压入新状态

	class Solution {

	public int minPushBox(char[][] grid) {
	int n = grid.length;
	int m = grid[0].length;
	// 使用 BFS，获取当前箱子位置相邻点 cx, cy, px, py
	// 判断人所在位置 px, py 到箱子相邻点与的对称点 sx, sy 是否可达

	// 找到箱子，人，目标点位置
	int x = 0, y = 0, px = 0, py = 0, tx = 0, ty = 0;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	if (grid[i][j] == 'B') {
	x = i;
	y = j;
	}
	if (grid[i][j] == 'S') {
	px = i;
	py = j;
	}
	if (grid[i][j] == 'T') {
	tx = i;
	ty = j;
	}
	}
	}
	int l = 0;
	// 去重，由于人可能来回走，所以需要 4 个状态
	Set<Pair> set = new HashSet<>();
	Deque<Pair> queue = new LinkedList<>();
	queue.addLast(new Pair(x, y, px, py));
	while (!queue.isEmpty()) {
	int size = queue.size();
	while (size-- > 0) {
	Pair pair = queue.pollFirst();
	if (pair.bx == tx && pair.by == ty) {
	return l;
	}
	if (set.contains(pair)) {
	continue;
	}
	set.add(pair);
	for (int i = 0; i < 4; i++) {
	// 箱子相邻点
	int cx = dx[i] + pair.bx;
	int cy = dy[i] + pair.by;
	// 对称点
	int sx = pair.bx - dx[i];
	int sy = pair.by - dy[i];
	// 有一方是箱子都不可以
	if (cx >= 0 && cy >= 0 && cx < n && cy < m && sx >= 0 && sy >= 0 && sx < n && sy < m) {
	if (grid[cx][cy] == '#' \|\| grid[sx][sy] == '#') {
	continue;
	}
	// 相邻点是否与人的距离可达
	if (canReachable(grid, cx, cy, pair.px, pair.py, pair.bx, pair.by, new boolean[n][m])) {
	// 对称点作为新箱子，原箱子作为人
	queue.addLast(new Pair(sx, sy, pair.bx, pair.by));
	}
	}
	}
	}
	l++;
	}
	return -1;
	}

	static int[] dx = new int[]{1, 0, 0, -1};
	static int[] dy = new int[]{0, 1, -1, 0};

	public boolean canReachable(char[][] grid, int x, int y, int ps, int py, int bx, int by, boolean[][] visited) {
	int n = grid.length;
	int m = grid[0].length;
	if (x < 0 \|\| x > n \|\| y < 0 \|\| y > m \|\| grid[x][y] == '#' \|\| x == bx && y == by \|\| visited[x][y]) {
	return false;
	}
	if (x == ps && y == py) {
	return true;
	}
	visited[x][y] = true;
	//x,y 是否可以到达 ps, py
	for (int i = 0; i < 4; i++) {
	// 相邻点
	int cx = dx[i] + x;
	int cy = dy[i] + y;
	if (cx >= 0 && cy >= 0 && cx < n && cy < m) {
	if (canReachable(grid, cx, cy, ps, py, bx, by, visited)) {
	return true;
	}
	}
	}
	return false;
	}

	}

	class Pair {
	int bx;
	int by;
	int px;
	int py;

	public Pair(int bx, int by, int px, int py) {
	this.bx = bx;
	this.by = by;
	this.px = px;
	this.py = py;
	}

	@Override
	public boolean equals(Object o) {
	if (this == o) return true;
	if (o == null \|\| getClass() != o.getClass()) return false;
	Pair pair = (Pair) o;
	return bx == pair.bx && by == pair.by && px == pair.px && py == pair.py;
	}

	@Override
	public int hashCode() {
	return Objects.hash(bx, by, px, py);
	}
	}

# BFS + 两个队列

定义 beforeQueue 作为箱子未移动，人移动所在的位置， afterQuque 作为箱子移动后的位置

遍历人所在位置的四个方向 cx , cy

若 cx , cy 等于箱子的位置 bx , by ，判断 cx , cy 关于箱子的对称点 sx , sy

若 sx , sy 是空点，则 sx , sy 作为新的箱子位置， bx , by 作为新的人所在位置，将该状态压入 afterQueue
若 cx , cy 不等于箱子的位置 bx , by ，则更新人的位置，箱子的位置不动，将该状态压入 beforeQueue

	class Solution {
	public int minPushBox(char[][] grid) {
	int n = grid.length;
	int m = grid[0].length;
	// 使用 BFS，获取当前箱子位置相邻点 cx, cy, px, py
	// 判断人所在位置 px, py 到箱子相邻点与的对称点 sx, sy 是否可达

	// 找到箱子与人位置
	int x = 0, y = 0, px = 0, py = 0, tx = 0, ty = 0;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	if (grid[i][j] == 'B') {
	x = i;
	y = j;
	}
	if (grid[i][j] == 'S') {
	px = i;
	py = j;
	}
	if (grid[i][j] == 'T') {
	tx = i;
	ty = j;
	}
	}
	}
	int l = 0;
	Set<Pair> set = new HashSet<>();
	// [箱子位置，人位置]
	Deque<Pair> beforeQueue = new LinkedList<>();
	beforeQueue.addLast(new Pair(x, y, px, py));
	while (!beforeQueue.isEmpty()) {
	Deque<Pair> afterQueue = new LinkedList<>();
	while (!beforeQueue.isEmpty()) {
	Pair pair = beforeQueue.pollFirst();
	if (pair.bx == tx && pair.by == ty) {
	return l;
	}
	if (set.contains(pair)) {
	continue;
	}
	set.add(pair);
	for (int i = 0; i < 4; i++) {
	// 人所在位置的相邻位置
	int cx = dx[i] + pair.px;
	int cy = dy[i] + pair.py;
	if (cx == pair.bx && cy == pair.by) {
	// 关于箱子的对称点
	int sx = pair.bx + dx[i];
	int sy = pair.by + dy[i];
	if (sx >= 0 && sy >= 0 && sx < n && sy < m && grid[sx][sy] != '#') {
	afterQueue.addLast(new Pair(sx, sy, pair.bx, pair.by));
	}
	} else {
	// 箱子不动，只更新人的状态
	if (cx >= 0 && cy >= 0 && cx < n && cy < m && grid[cx][cy] != '#') {
	beforeQueue.addLast(new Pair(pair.bx, pair.by, cx, cy));
	}
	}
	}
	}
	beforeQueue = afterQueue;
	l++;
	}
	return -1;
	}

	static int[] dx = new int[]{1, 0, 0, -1};
	static int[] dy = new int[]{0, 1, -1, 0};


	}

	class Pair {
	int bx;
	int by;
	int px;
	int py;

	public Pair(int bx, int by, int px, int py) {
	this.bx = bx;
	this.by = by;
	this.px = px;
	this.py = py;
	}

	@Override
	public boolean equals(Object o) {
	if (this == o) return true;
	if (o == null \|\| getClass() != o.getClass()) return false;
	Pair pair = (Pair) o;
	return bx == pair.bx && by == pair.by && px == pair.px && py == pair.py;
	}

	@Override
	public int hashCode() {
	return Objects.hash(bx, by, px, py);
	}
	}

最短路困难广度优先搜索

# BFS + DFS

# BFS + 两个队列

前往目标的最小代价

提取咒文