Push The Box To The Target

The character ‘P’ represents the player. The player can move only in four directions, up, down, left, and right only if the is a floor. The character ‘T’ represents the target location. The character ‘B’ represents the box. There is only one box in the grid. The player can not move through the box. The character ‘.’ represents the floor which means a free cell to walk. The character ‘|’ represents the wall which means an obstacle.

You are given grid = [["|","|","|","|","|","|"], ["|","T",".","B",".","|"], ["|",".","|","|",".","|"], ["|",".",".",".","S","|"], ["|","|","|","|","|","|"]] The answer will be 2. The player has to push the box two times to move it to the target location.

The first line contains an integer 'C' which denotes the number of test cases. The first line of each test case contains two space-separated integers, ‘M’ and ‘N’, representing the number of rows and columns, respectively. The next ‘M’ line contains ‘N’ space-separated integers representing the ‘GRID’.

1 <= C <= 10 1 <= M, N <= 20 GRID contains only characters ‘P’, ‘T’, ‘B’, ‘|’, or ‘.’. There is only one character, ‘P’, ‘T’, and ‘B’ in the GRID. Time limit: 1 sec

For the first test case, the answer will be 2. The player has to push the box two times to move it to the target location. For the second test case, the answer will be 1. The player has to push the box only once to move it to the target location.

Breadth-First Search

As we already know, the BFS can be used to find the shortest path from a source location to the target location. But that is not enough to solve this problem because we can move a box only if the player is in the opposite adjacent cell to the cell where we have to move the box. For example, if we have to move the box up the player should be below the box. So, to overcome this, we will initialize a queue that will store the state of the box and the player. Then for each state, we will check if the target location is reachable or not using another BFS.

Structure of graph created: Any vertice V denotes a game state and edge E denotes transition between states.

Algorithm:

Maintain a class Pair with two fields, T first and E second, where T and E can be any type.
Intialize a 2D array dirs with value {{-1,0},{0,1},{1,0},{0,-1}}.
Initialize a Pair box and a Pair player.
Iterate i in 0 to m
- Itertate j in 0 to n
  - If grid[i][j] is ‘B’
    - Set box.first as i;
    - Set box.second as j;
  - Else if grid[i][j] is ‘P’
    - Set player.first as i;
    - Set player.second as j;
Initialize a queue that will store a Pair of two Pairs. First Pair represents the state of the box, and the second Pair represents the player’s state.
Add state of box and player to the queue.
Create a 2D array visited to keep track of visited cells.
Initialize a variable push with a value 0. This variable will store the number of pushes.
Increment push by one.
Iterate i in (queue.size - 1) to 0
- Initialize a variable state to store the current state.
- Initialize a variable b to store the current state of the box.
- Initialize a variable p to store the current state of the player.
- Iterate j in dirs.
  - Initialize a variable nb to store the next state of the box.
  - Set nb.first as b.first + dirs[j][0]
  - Set nb.second as b.second + dirs[j][1]
  - If there is no obstacle at next state of box and it is inside the bounds. i,e, if (nb.first >= 0 && nb.first < m && nb.second >= 0 && nb.second < n && grid[nb.first][nb.second] != '|') {
    - Initialize a new variable np to store the next state of the player.
    - Set np.first as b.first - dirs[j][0]
    - Set np.second as b.second - dirs[j][1]
    - If there is no obstacle at next state of player and it is inside the bounds i.e, if (np.first >= 0 && np.first < m && np.second >= 0 && np.second < n && grid[np.first][np.second] != '|' && !visited[nb.first * n + nb.second][np.first * n + np.second])
      - Check if target is reachable. If yes:
        If grid[nb.first][nb.second] is equal to 'T'
        return push
        Mark current state true.
        Set visited[nb.first * n + nb.second][np.first * n + np.second] as true;
        queue.add(new Pair<>(nb, b))
Return -1.
Maintain a function isReachable(char[][] grid, int m, int n, Pair box, Pair from, Pair to)
- Initialize a queue.
- Initialize a array visited of size m*n
- Set visited[from.first][from.second] as true
- Iterate while queue is not empty.
  - Initialize a variable loc with head of queue and remove head of queue.
  - If current cell is target cell, i.e,if (loc.first == to.first && loc.second == to.second), return true.
  - Iterate j in dirs
    - Initialize a variable nr with value loc.first + dirs[j][0].
    - Initialize a variable nc with value loc.second + dirs[j][1].
    - Check next row and next cloumn is free cell. if (nr >= 0 && nr <m && nc >= 0 && nc < n && !visited[nr][nc]&& grid[nr][nc] != '|'&& (nr != box.first || nc != box.second))
      - Set visited[nr][nc] as true;
      - queue.add(new Pair<>(nr, nc));
- Return false.

Time Complexity

O((M * N)^2), where M and N are numbers of rows and columns of the grid, respectively.

There can be a total of 4 * (M * N) game states in the worst case. For every state, we will check if it is possible to reach the target location which requires checking 4 * (M * N) states. Hence, the total time complexity will be O((M * N)^2).

Space Complexity

O(M * N), where M and N are numbers of rows and columns of the grid, respectively.

The total space used by the queues in main minPushes() and isReachable() in the worst case is (M * N). Hence total space complexity is O(M * N).

Problem statement

Sample Input 1:

Sample Output 1:

Explanation:

Sample Input 2:

Sample Output 2: