Minimum Moves to Move a Box to Their Target Location

• Initialize a global variable min_pushes to infinity.
• Define a recursive function, for example, dfs(box_r, box_c, player_r, player_c, current_pushes).
• To avoid infinite loops, use a visited set to track states (box_pos, player_pos) within the current recursion path. Add the current state to the set before making recursive calls and remove it after they return.
• Pruning Step: If current_pushes is already greater than or equal to min_pushes, there is no need to explore further down this path, so return immediately.
• Base Case: If the box's position (box_r, box_c) matches the target location, it means a valid path has been found. Update min_pushes = min(min_pushes, current_pushes) and return.
• Recursive Step:
  1. Explore Player Moves: For each of the four directions, if the player can move to a new cell (npr, npc) (i.e., it's a floor and not the box's location) and the new state (box_r, box_c, npr, npc) has not been visited in the current path, make a recursive call: dfs(box_r, box_c, npr, npc, current_pushes).
  2. Explore Box Pushes: If the player is adjacent to the box, they can attempt to push it. For each valid push that moves the box to (new_br, new_bc) and the player to the box's old spot (box_r, box_c), and the new state has not been visited, make a recursive call: dfs(new_br, new_bc, box_r, box_c, current_pushes + 1).
• The initial call to the function would be with the starting positions of the box and player, and current_pushes as 0.
• After the initial call returns, if min_pushes is still infinity, it means the target is unreachable; otherwise, it holds the minimum number of pushes.

The core of this method is a recursive Depth First Search (DFS) function that explores the state space. A state is defined by the tuple (box_row, box_col, player_row, player_col). The function systematically tries every possible move from the current state.

There are two types of moves:

1. Player Move: The player moves to an adjacent empty cell. This does not increase the push count.
2. Box Push: The player, standing next to the box, pushes it to an adjacent empty cell. This increases the push count by one.

The recursion continues until the box reaches the target. To prevent infinite loops (e.g., moving the player back and forth), we must keep track of the states visited in the current path. This approach is exhaustive and, without memoization (which would transform it into a dynamic programming solution), it is highly inefficient as it explores many redundant paths.

• First, parse the grid to find the initial positions of the player 'S', the box 'B', and the target 'T'.
• Define a state as a tuple (box_row, box_col, player_row, player_col).
• Initialize a 4D array, dist[m][n][m][n], with a large value (infinity) to store the minimum pushes to reach each state. This array also implicitly acts as a visited array.
• Initialize a deque (double-ended queue) for the 0-1 BFS.
• Add the initial state (start_br, start_bc, start_pr, start_pc) to the front of the deque and set its distance in the dist array to 0.
• While the deque is not empty:
  • Pop a state (br, bc, pr, pc) from the front of the deque. Let its distance be d.
  • If (br, bc) is the target position, return d.
  • Explore Player Moves (0-cost transitions): For each of the 4 neighbors (npr, npc) of the player at (pr, pc):
    • If the move is valid (within bounds, not a wall, and not the box's current location) and d < dist[br][bc][npr][npc]:
    • Update dist[br][bc][npr][npc] = d.
    • Add the new state (br, bc, npr, npc) to the front of the deque.
  • Explore Box Pushes (1-cost transitions): If the player at (pr, pc) is adjacent to the box at (br, bc):
    • Calculate the new box position (nbr, nbc) by pushing it away from the player.
    • If the push is valid (the new box position is within bounds and not a wall) and d + 1 < dist[nbr][nbc][br][bc]:
    • Update dist[nbr][nbc][br][bc] = d + 1.
    • The new player position is the box's old spot (br, bc). Add the new state (nbr, nbc, br, bc) to the back of the deque.
• If the deque becomes empty and the target has not been reached, it's impossible to solve. Return -1.

The state of the system can be fully described by (box_row, box_col, player_row, player_col). We can think of each unique state as a node in a giant graph. Our goal is to find the shortest path from the initial state to any state where the box is on the target location.

The transitions between states (edges in the graph) have costs:

• Player Move: When the player moves without pushing the box, the state changes, but the number of pushes does not. This is a 0-cost edge.
• Box Push: When the player pushes the box, the state changes, and the number of pushes increases by one. This is a 1-cost edge.

A 0-1 BFS is an ideal algorithm for this scenario. It uses a deque (double-ended queue). When exploring a state, new states reached via 0-cost edges (player moves) are added to the front of the deque, while states reached via 1-cost edges (box pushes) are added to the back. This ensures that we always explore all possible free player movements for a given number of pushes before considering the next push. This correctly finds the path with the minimum number of pushes.

We use a 4D array to store the minimum pushes to reach any state, which also helps us avoid visiting the same state with a higher or equal push count.

1import java.util.ArrayDeque;2import java.util.Arrays;3import java.util.Deque;4 5class Solution {6    public int minPushBox(char[][] grid) {7        int m = grid.length, n = grid[0].length;8        int[] sPos = null, bPos = null, tPos = null;9 10        for (int i = 0; i < m; i++) {11            for (int j = 0; j < n; j++) {12                if (grid[i][j] == 'S') {13                    sPos = new int[]{i, j};14                    grid[i][j] = '.'; // Treat player's start as floor15                } else if (grid[i][j] == 'B') {16                    bPos = new int[]{i, j};17                    grid[i][j] = '.'; // Treat box's start as floor18                } else if (grid[i][j] == 'T') {19                    tPos = new int[]{i, j};20                    grid[i][j] = '.'; // Treat target as floor21                }22            }23        }24 25        int[][][][] dist = new int[m][n][m][n];26        for (int i = 0; i < m; i++) {27            for (int j = 0; j < n; j++) {28                for (int k = 0; k < m; k++) {29                    Arrays.fill(dist[i][j][k], Integer.MAX_VALUE);30                }31            }32        }33 34        Deque<int[]> deque = new ArrayDeque<>();35        36        dist[bPos[0]][bPos[1]][sPos[0]][sPos[1]] = 0;37        deque.addFirst(new int[]{bPos[0], bPos[1], sPos[0], sPos[1]});38 39        int[] dr = {-1, 1, 0, 0};40        int[] dc = {0, 0, -1, 1};41 42        while (!deque.isEmpty()) {43            int[] current = deque.pollFirst();44            int br = current[0], bc = current[1];45            int pr = current[2], pc = current[3];46            int d = dist[br][bc][pr][pc];47 48            if (br == tPos[0] && bc == tPos[1]) {49                return d;50            }51 52            // Player moves (cost 0)53            for (int i = 0; i < 4; i++) {54                int npr = pr + dr[i];55                int npc = pc + dc[i];56 57                if (npr >= 0 && npr < m && npc >= 0 && npc < n && grid[npr][npc] != '#' && !(npr == br && npc == bc)) {58                    if (dist[br][bc][npr][npc] > d) {59                        dist[br][bc][npr][npc] = d;60                        deque.addFirst(new int[]{br, bc, npr, npc});61                    }62                }63            }64 65            // Box pushes (cost 1)66            if (Math.abs(pr - br) + Math.abs(pc - bc) == 1) { // Player is adjacent to the box67                int nbr = br + (br - pr);68                int nbc = bc + (bc - pc);69 70                if (nbr >= 0 && nbr < m && nbc >= 0 && nbc < n && grid[nbr][nbc] != '#') {71                    if (dist[nbr][nbc][br][bc] > d + 1) {72                        dist[nbr][nbc][br][bc] = d + 1;73                        deque.addLast(new int[]{nbr, nbc, br, bc});74                    }75                }76            }77        }78 79        return -1;80    }81}