Java - Dual BFS
\n// We need to track the min number of steps that the box needs to be pushed to the target\n// We don\'t care how many steps the player takes\n// We will track
```\n// We need to track the min number of steps that the box needs to be pushed to the target\n// We don\'t care how many steps the player takes\n// We will track the state of the box and the player\n// For every box position we consider each possible next box position\n//    - The usual checks, is the box position in bounds, visited, not a wall, etc. plus...\n//    - Can the player be moved into position to move the box to the new position? Use separate BFS\n// We track the visited position and direction of the box\n// 4 ms, faster than 99.60%\nclass State {\n  int pRow;\n  int pCol;\n  int bRow;\n  int bCol;\n  State() {}\n  State(int pRow, int pCol, int bRow, int bCol) {\n    this.pRow = pRow;\n    this.pCol = pCol;\n    this.bRow = bRow;\n    this.bCol = bCol;\n  }\n}\nclass Solution {\n  private static final int[][] DIRS = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};\n  public int minPushBox(char[][] grid) {\n    int rows = grid.length;\n    int cols = grid[0].length;\n    State initState = new State();\n    for (int row = 0; row < rows; row++) {\n      for (int col = 0; col < cols; col++) {\n        if (grid[row][col] == \'S\') {\n          initState.pRow = row;\n          initState.pCol = col;\n        } else if (grid[row][col] == \'B\') {\n          initState.bRow = row;\n          initState.bCol = col;\n        }\n      }\n    }\n    boolean[][][] visited = new boolean[rows][cols][4];\n    Deque<State> deque = new ArrayDeque<>();\n    deque.add(initState);\n    int steps = 1;\n    while (!deque.isEmpty()) {\n      int size = deque.size();\n      for (int i = 0; i < size; i++) {\n        State curr = deque.remove();\n        for (int dir = 0; dir < 4; dir++) {\n          int adjBRow = curr.bRow + DIRS[dir][0];\n          int adjBCol = curr.bCol + DIRS[dir][1];\n          // player must have been in this position to push box to new adj position\n          int adjPRow = curr.bRow - DIRS[dir][0]; \n          int adjPCol = curr.bCol - DIRS[dir][1];\n          if (adjBRow < 0 || adjBRow > rows - 1 || adjBCol < 0 || adjBCol > cols - 1 || \n             adjPRow < 0 || adjPRow > rows - 1 || adjPCol < 0 || adjPCol > cols - 1 ||\n              visited[adjBRow][adjBCol][dir] || \n              grid[adjBRow][adjBCol] == \'#\' || grid[adjPRow][adjPCol] == \'#\' || \n             !playerCanReachBox(grid, curr.pRow, curr.pCol, adjPRow, adjPCol, curr.bRow, curr.bCol))\n            continue;\n          if (grid[adjBRow][adjBCol] == \'T\')\n            return steps;\n          visited[adjBRow][adjBCol][dir] = true;\n          deque.add(new State(curr.bRow, curr.bCol, adjBRow, adjBCol));\n        }\n      }\n      steps++;\n    }\n    return -1;\n  }\n  private boolean playerCanReachBox(char[][] grid, int pRow1, int pCol1, int pRow2, int pCol2, int bRow, int bCol) {\n    int rows = grid.length;\n    int cols = grid[0].length;\n    if (pRow1 == pRow2 && pCol1 == pCol2)\n      return true;\n    Deque<Integer> deque = new ArrayDeque<>();\n    deque.add(pRow1 * cols + pCol1);\n    boolean[][] visited = new boolean[rows][cols];\n    visited[pRow1][pCol1] = true;\n    visited[bRow][bCol] = true;\n    while (!deque.isEmpty()) {\n      int index = deque.remove();\n      int row = index / cols;\n      int col = index % cols;\n      for (int[] dir : DIRS) {\n        int adjRow = row + dir[0];\n        int adjCol = col + dir[1];\n        if (adjRow < 0 || adjRow > rows - 1 || adjCol < 0 || adjCol > cols - 1 ||\n            visited[adjRow][adjCol] || grid[adjRow][adjCol] == \'#\')\n          continue;\n        if (adjRow == pRow2 && adjCol == pCol2)\n          return true;\n        deque.add(adjRow * cols + adjCol);\n        visited[adjRow][adjCol] = true;\n      }\n    }\n    return false;\n  }\n}\n```
[]