Last Updated: 4 Apr, 2021
Spreading Smoke
Easy
Asked in companies
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)
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
Approaches
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-
- We will initially initialize Distace[N][M] to infinity.
- We will initialise Distace[X][Y] to 1.
- 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
- Ans = -1
Ans stores the final answer
- While (size of Queue > 0)
- a, b = Queue.pop()
- ans=Distance[a][b]
- For all not visited adjacent cells
- 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
- Distance[adjacent-x][adjacent-y]=Distance[a][b]+1
- Queue.push((ad-x,ad-y))
We will add the adjacent the cell to queue