Spreading Smoke

Easy
0/40
Average time to solve is 26m
profile
Contributed by
2 upvotes
Asked in companies
Snapdeal Ltd.Gainsight

Problem statement

You are given a room as a grid of 1’s and 0’s. 1 indicating blocked cell and 0 indicating a free cell. There is a bomb in the X'th row from the top and Y’th column from the left. The bomb went off and smoke was starting to spread. In one sec smoke can spread to an adjacent cell if the adjacent cell has 0 in it. The bomb is always at the free cell.

Find the minimum time for the smoke to spread across all the reachable cells. A cell is reachable from another cell if you can travel from one cell to another via cells containing 0’s.

Cells are adjacent if they share a common edge.

For example:

 GRID=[[1,1,0,1],
       [1,0,0,0],
       [1,1,0,1]]
X,Y= (2, 3)
ANS = 2
In 1’st sec smoke will spread to (1, 3), (3, 3), (2, 2), (2, 4) 
In 2’nd sec smoke will spread to (2, 1)
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains four space-separated integers ‘N’, ‘M’, ‘X’, ‘Y’, dimensions of the room and the co-ordinate of the bomb.

The next N lines of each test cases contain M space-separated integers denoting the elements of the grid.
Output Format : 
For each test case print the minimum amount of time taken by the room to spread across all the reachable cells.

Output for each test case is printed in a separate line.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 5
1 <= N, M <= 500
1 <= X <= N
1 <= Y <=M

Time Limit: 1 sec
Sample Input 1 :
2
2 2 1 1
0 0
1 0
1 7 1 6
0 0 0 0 0 0 0
Sample Output 1 :
2
5
Explanation of Sample Input 1 :
Lets denote a cell by S if it have smoke 
For the first test , 
At time 0
GRID=[[S, 0],
      [1, 0]]

At time 1
GRID=[[S, S],
      [1, 0]]
At time 2
GRID=[[S, S],
      [1, S]]

For the second test case, it will take 5 sec for the smoke to travel from (1,6) to (0,0)
Sample Input 2 :
2 
5 5 5 5 
0 0 0 0 0
1 1 1 1 0
0 0 0 0 0
0 1 1 1 1
0 0 0 0 0
5 5 3 3
0 0 0 0 0
1 1 1 1 0
0 0 0 1 0
0 1 1 1 0
0 0 0 0 0
Sample Output 2 :
16
16
Hint

Can we use a breadth-first search to find the Minimum time for the smoke to spread ??

Approaches (1)
BFS

We will use a breadth-first search to find the cell which is reachable from the bomb and farthest from the bomb. We will start our BFS from the location at expanding to the four adjacent cells if there are not visited so far. 

For each cell, we will also maintain the smallest distance from the bomb. 

The algorithm will be-

  1. We will initially initialize Distace[N][M] to infinity.
  2. We will initialise Distace[X][Y] to 1.
  3. Queue = [(X, Y)]

           This queue stores all the unprocessed cells, we will pop a cell from the queue and try to move to an adjacent cell

  1. Ans = -1

           Ans stores the final answer 

  1. While (size of Queue > 0)
    1. a, b = Queue.pop()
    2. ans=Distance[a][b]
    3. For all not visited adjacent cells
      1. If  Grid[a][b]==0 and Distance[a][b]== infinity

           We will try to visit all the adjacent cells if the distance of adjacent cells is infinity then this cell is not visited yet 

  1. Distance[adjacent-x][adjacent-y]=Distance[a][b]+1
  2. Queue.push((ad-x,ad-y))

We will add the adjacent the cell to queue 

Time Complexity

O(N*M)  where ‘N’, ‘M’,  is the dimensions of the room.

    We are visiting each cell location exactly once.

Space Complexity

    O(N*M)  where ‘N’, ‘M’,  is the dimensions of the room.

    Space required to store the Distance and Queue array/list.

Code Solution
(100% EXP penalty)
Spreading Smoke
Full screen
Console