[Java] BFS + DFS with explanation
The idea is using BFS find the shortest path from the box location to the destination.\nHowever, each time we check if the box can be moved we need to check 2 p
The idea is using BFS find the shortest path from the box location to the destination.\nHowever, each time we check if the box can be moved we need to check 2 position\n![image](https://assets.leetcode.com/users/lnbyk/image_1574563041.png)\n\nThe Box is just the box and the cycle is the position we need check\nWhen we want to move box to left we need check if the position both the cell at the left of the box and right of the box is ok. And we need to do the same thing for four directions.\n\nDFS:\n\tThe reason use DFS is to check if the person can move to the position where he can move the box.\n\tSuch as below \n\t![image](https://assets.leetcode.com/users/lnbyk/image_1574563377.png)\n\tThe green arrow is just the one of the path we need to check if person can move.\n\n\n```\nclass Solution {\n    private class Sugarcane{\n        int box;\n        int person;\n        public Sugarcane(int box, int person){\n            this.box = box;\n            this.person = person;\n        }\n        public String toString(){\n            return this.box + " " + this.person;\n        }\n    }\n    \n    Set<Integer> set = new HashSet<>();\n    int[] dir = {0, 1, 0, -1, 0};\n    int m, n;\n    public int minPushBox(char[][] grid) {\n        int res = -1;\n        m = grid.length; n = grid[0].length;\n        int d = 0, p = 0;\n        Queue<Sugarcane> queue = new LinkedList<>();\n        Set<String> visited = new HashSet<>();\n        \n        for(int i = 0; i < m; i++){\n            for(int j = 0; j < n; j++){\n                if(grid[i][j] == \'B\'){\n                    d = i * n + j;\n                }\n                else if(grid[i][j] == \'S\'){\n                    p = i * n + j; \n                }\n            }\n        }\n        Sugarcane sugarcane = new Sugarcane(d, p);\n        queue.offer(sugarcane);\n        visited.add(sugarcane.toString());\n        \n        while(!queue.isEmpty()){\n            int size = queue.size();\n            res++;\n            for(int i = 0; i < size; i++){\n                Sugarcane sugar = queue.poll();\n                int bp = sugar.box, pp = sugar.person;\n                int x = bp / n, y = bp % n;\n                if(grid[x][y] == \'T\')\n                    return res;\n                \n                grid[x][y] = \'#\';\n                for(int j = 0; j < 4; j++){\n                    int bx = x + dir[j], by = y + dir[j + 1];\n                    int px = x - dir[j], py = y - dir[j + 1];\n                    Sugarcane nextSugar = new Sugarcane(bx * n + by, px * n + py);\n                    String nV = nextSugar.toString();\n                    set = new HashSet<>();\n                    if(isVaild(bx, by, grid) && !visited.contains(nV) && dfs(pp / n, pp % n, grid, px, py)){\n                        queue.offer(nextSugar);\n                        visited.add(nV);\n                    }\n                }\n                grid[x][y] = \'.\';\n            }\n        }\n        return -1;\n    }\n    \n    \n    public boolean isVaild(int x, int y, char[][] grid){\n        return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] != \'#\';\n    }\n    \n    public boolean dfs(int x, int y, char[][] grid, int dx, int dy){\n        if(x == dx && y == dy)\n            return true;\n        for(int i = 0; i < 4; i++){\n            int nx = x + dir[i], ny = y + dir[i + 1];\n            if(isVaild(nx, ny, grid) && set.add(nx * n + ny))\n                if(dfs(nx, ny, grid, dx, dy))\n                    return true;\n        }\n        return false;\n    }\n}\n```
[]