『Leetcode 5266』推箱子

本文主要是介绍『Leetcode 5266』推箱子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

『题目』：

给「推箱子」是一款风靡全球的益智小游戏，玩家需要将箱子推到仓库中的目标位置。
游戏地图用大小为 n * m 的网格 grid 表示，其中每个元素可以是墙、地板或者是箱子。
现在你将作为玩家参与游戏，按规则将箱子 'B' 移动到目标位置 'T' ：

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

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

『限制条件』：

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

『输入输出』

输入：grid = [["#","#","#","#","#","#"],["#","T","#","#","#","#"],["#",".",".","B",".","#"],["#",".","#","#",".","#"],["#",".",".",".","S","#"],["#","#","#","#","#","#"]]
输出：3
解释：我们只需要返回推箱子的次数。输入：grid = [["#","#","#","#","#","#"],["#","T","#","#","#","#"],["#",".",".","B",".","#"],["#","#","#","#",".","#"],["#",".",".",".","S","#"],["#","#","#","#","#","#"]]
输出：-1输入：grid = [["#","#","#","#","#","#"],["#","T",".",".","#","#"],["#",".","#","B",".","#"],["#",".",".",".",".","#"],["#",".",".",".","S","#"],["#","#","#","#","#","#"]]
输出：5
解释：向下、向左、向左、向上再向上。输入：grid = [["#","#","#","#","#","#","#"],["#","S","#",".","B","T","#"],["#","#","#","#","#","#","#"]]
输出：-1

『题解』：

两次bfs，首先假设可以推动1次，那么block可以

向左（人要在block右边）
向右（人要在block左边）
向上（人要在block下边）
向下（人要在block上边）

那么第一个bfs就要知道人可不可以到达block移动时所要求的位置，这个bfs完全可以随机遍历，复杂度O( $n m$ )，要注意block和#的位置都不可以走过去。
那么第二个bfs要考虑的问题就是移动block，这里不能用二维标记来记录block走过的路，要注意下面一种情况：

这里的解决方案是先将block左移一次，然后人再从K的位置走出去，再把箱子移回到K，然后走到S‘才能把block推到T位置上。可是这个过程K位置访问过2次，所以标记状态的时候，需要四维数组记录最后人的状态，这样就可以重复地进入K了。复杂度为O( $n^2m^2$ )。总复杂度最大为O( $n^3m^3$ ) 约等于6400W次操作，刚好符合程序运行要求。

『实现』：

import java.time.Period;
import java.util.LinkedList;
import java.util.Queue;public class test11 {// 上，下，左，右int[] bdx = {-1, 1, 0, 0};int[] bdy = {0, 0, -1, 1};int[] pdx = {1, -1, 0, 0};int[] pdy = {0, 0, 1, -1};class Point {int bx,by;int px,py;int step;public Point(int bx, int by, int px, int py, int step) {this.bx = bx;this.by = by;this.px = px;this.py = py;this.step = step;}}class Person{int px,py;public Person(int px, int py) {this.px = px;this.py = py;}}Point pos;int ans;public boolean bfsP(char[][] grid, int n, int m,int px,int py,int targetx, int targety,int bx,int by) {boolean[][] flag = new boolean[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {flag[i][j] = false;}}Queue<Person> queue = new LinkedList<>();queue.offer(new Person(px,py));flag[px][py] = true;while (!queue.isEmpty()){Person tmp = queue.poll();if(tmp.px == targetx && tmp.py == targety) return true;if(tmp.px == bx && tmp.py == by) continue;for(int i = 0;i < 4;i++){int ptmpx = tmp.px + pdx[i];int ptmpy = tmp.py + pdy[i];if(check(ptmpx,ptmpy,n,m,grid) && flag[ptmpx][ptmpy] == false){flag[ptmpx][ptmpy] = true;queue.offer(new Person(ptmpx,ptmpy));}}}return false;}public void bfsB(char[][] grid, int n, int m) {boolean[][][][] flag = new boolean[n][m][n][m];for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)for(int ii = 0;ii < n;ii++)for(int jj = 0;jj < m;jj++)flag[i][j][ii][jj] = false;Queue<Point> queue = new LinkedList<>();queue.offer(pos);flag[pos.bx][pos.by][pos.px][pos.py] = true;while (!queue.isEmpty()){Point tmp = queue.poll();if(grid[tmp.bx][tmp.by] == 'T'){ans = tmp.step;return;}for(int i = 0;i < 4;i++){int btmpx = tmp.bx + bdx[i];int btmpy = tmp.by + bdy[i];int ptmpx = tmp.bx + pdx[i];int ptmpy = tmp.by + pdy[i];if(check(btmpx,btmpy,n,m,grid) && check(ptmpx,ptmpy,n,m,grid) && flag[btmpx][btmpy][ptmpx][ptmpy] == false){if(bfsP(grid,n,m,tmp.px,tmp.py,ptmpx,ptmpy,tmp.bx,tmp.by)){flag[btmpx][btmpy][ptmpx][ptmpy] = true;queue.offer(new Point(btmpx,btmpy,tmp.bx,tmp.by,tmp.step + 1));}}}}}public boolean check(int x,int y,int n,int m,char[][] grid){if(x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == '#')return false;return true;}public int minPushBox(char[][] grid) {int n = grid.length;int m = grid[0].length;ans = -1;int bx=0,by=0,px=0,py=0;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (grid[i][j] == 'B'){bx = i;by = j;}else if (grid[i][j] == 'S'){px = i;py = j;}}}pos = new Point(bx,by,px,py,0);bfsB(grid, n, m);return ans;}public static void main(String[] args) {char[][] grid = {{'#','.','.','#','T','#','#','#','#'},{'#','.','.','#','.','#','.','.','#'},{'#','.','.','#','.','#','B','.','#'},{'#','.','.','.','.','.','.','.','#'},{'#','.','.','.','.','#','.','S','#'},{'#','.','.','#','.','#','#','#','#'}};test11 of = new test11();System.out.println(of.minPushBox(grid));}
}