# 1263. Minimum Moves to Move a Box to Their Target Location
###### tags: `Leetcode` `Hard` `BFS` `DFS`
Link: https://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location/description/
## 思路
思路[参考](https://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location/solutions/709355/java-use-2-level-bfs-beat-99/)
可以想到的是用bfs解决这个问题
但是问题是
1. 我们要保证人有位置可以推box 并且从现在人站的位置到推box的位置是有路可以走的 所以这时我们就需要另外一个bfs来判断有没有路可以走
2. 由于我们是不能跨越盒子的所以在里面这个bfs我们要把盒子当作一个block(通过把目前放盒子的点的visited设成true)
3. 2d的visited array是不够的 因为盒子会移动 所以可能在某个位置原本向左是走不通的但现在是可以的
## Code

class Solution {
    public int minPushBox(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] start = new int[2];
        int[] end = new int[2];
        int[] ppl = new int[2];
        int[][] dirs = new int[][]{{-1,0},{1,0},{0,1},{0,-1}};
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j]=='T') end = new int[]{i,j};
                else if(grid[i][j]=='S') ppl = new int[]{i,j};
                else if(grid[i][j]=='B') start = new int[]{i,j};
            }
        }
        boolean[][][] visited = new boolean[m][n][4];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{start[0], start[1], ppl[0], ppl[1]});
        int step = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i=0; i<size; i++){
                int[] curr = q.poll();
                if(curr[0]==end[0] && curr[1]==end[1]) return step;
                for(int j=0; j<dirs.length; j++){
                    if(visited[curr[0]][curr[1]][j]) continue;
                    int[] dir = dirs[j];
                    int r0 = curr[0]+dir[0], c0 = curr[1]+dir[1];
                    if(r0<0 || r0>=m || c0<0 || c0>=n || grid[r0][c0]=='#') continue;
                    int nextx = curr[0]-dir[0], nexty = curr[1]-dir[1];
                    if(nextx<0 || nextx>=m || nexty<0 || nexty>=n || grid[nextx][nexty]=='#') continue;
                    if(!canReach(r0, c0, curr, grid)) continue;
                    visited[curr[0]][curr[1]][j] = true;
                    q.add(new int[]{nextx, nexty, r0, c0});
                }
            }
            step++;
        }
        return -1;
    }
    private boolean canReach(int r, int c, int[] pos, char[][] grid){
        int x = pos[2], y = pos[3];
        int m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        visited[x][y] = true;
        visited[pos[0]][pos[1]] = true;
        Queue<int[]> q = new LinkedList<>();
        int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        q.add(new int[]{x,y});
        while(!q.isEmpty()){
            int[] curr = q.poll();
            if(curr[0]==r && curr[1]==c) return true;
            for(int[] dir:dirs){
                int nextx = curr[0]+dir[0];
                int nexty = curr[1]+dir[1];
                if(nextx>=0 && nextx<m && nexty>=0 && nexty<n && !visited[nextx][nexty] && grid[nextx][nexty]!='#'){
                    q.add(new int[]{nextx, nexty});
                    visited[nextx][nexty] = true;
                }
            }
        }
        return false;
    }
}