Last Updated: 8 Oct, 2021

Push The Box To The Target

Hard

Asked in company

Problem statement

Ninja is playing a game where the player has to move a box to the target location. The game is represented by a ‘M x N’ grid ‘GRID’ of characters (‘P’, ‘T’, ‘B’, ‘|’, ‘.’), where:

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.

The box can be pushed to an adjacent free cell by standing next to the box and then moving in the direction of the box.

Your task is to return the minimum number of pushes to move the box to the target. If there is no way to reach the target location, return -1.

For example:

 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.

Input Format:

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’.

Output Format:

For each test case, print a single integer, denoting the minimum number of pushes required to move the box to the target location.

The output of each test case will be printed in a separate line.

Constraints:

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

Note:

You do not need to input or print anything, as it has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

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.

Solve now