Problem

Submissions

Hints & solutions

Discuss

Fire in the cells.

Hard

0/120

Average time to solve is 15m

Contributed by

52 upvotes

Asked in companies

Problem statement

You are given a matrix 'MAT' of size ‘N’ * ‘M’, where ‘N’ is the number of rows and ‘M’ is the number of columns. Value ‘0’ in a cell represents that the cell is set on fire initially, (at time t = ‘0’), and the cells which don’t have fire initially have value = ‘1’, and are called safe cells.

If a cell is on fire, then in one second the fire will expand to its adjacent cells (left, right, top, bottom) if they are not already on fire.

You are given the position of a person as integers ‘X’ and ‘Y’ denoting the cell (‘X’, ‘Y’). In one second the person can move from its current cell to any one of its adjacent cells, provided they are not on fire.

You have to determine if the person can move through the matrix to one of the escape cells without burning himself i.e. without going through the fire cells. If it’s possible, return time taken, else return -1.

Note:

1. Escape cells in this problem are all such cells that lie on the edge of the matrix but not on the corner. i.e all such cells which are in the first row, first column, last row, and last column excluding the four corner cells are considered as valid escape cells.

2. A cell once set on fire continues to remain on fire till the end.

3. Note that rows are indexed from 0 to ‘N’ - 1 and columns are indexed from 0 to ‘M’ - 1.

4. The escape cells may also be initially on fire or can catch fire from some neighboring cell.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘M’, where ‘N’ denotes the number of rows in the given matrix and ‘M’ denotes the number of columns in the given matrix.

Each of the next ‘N’ lines contains ‘M’ space-separated integers (‘0’ or ‘1’) denoting the initial condition of cells.

The last line of each test case contains two space-separated integers ‘X’ and ‘Y’, where ‘X’ denotes the initial row of the person at time t = 0 and ‘Y’ denotes the initial column of the person at time t = 0.

Output Format:

For each test case, print an integer ‘K’ representing the time taken by the person to reach the escape cell. If the person cannot reach the escape cell then print -1.

Output for each test case will be printed in a separate line.

Note:

You are not required to print the output, it has already been taken care of. Just implement the function.

Constraints:

1 <= 'T' <= 50
0 <= 'N' < 50
0 <= 'M' < 50
0 <= 'X' <= N
0 <= 'Y' <= M

Time Limit: 1 sec

Sample Input 1:

Sample Output 1:

-1

Explanation For Sample Output 1:

The time for the fire to reach the individual cells of the given matrix is as follows:

The person’s initial cell is (2, 1).
At time t = 1, the person can only go to cell (2, 2) as the fire won’t have reached the cell yet.
At time t = 2, the person can not go anywhere as all the adjacent cells are at the fire, and moving causes him to get burnt.
So the answer is -1.

Sample Input 2:

Sample Output 2:

Hint 1

What if you find the minimum time the fire will reach every cell in the matrix using BFS? And if you possess this information can you try to find if a valid path exists for a person to escape or not?

Approaches (1)

Approach 1

Multisource BFS

With each passing second fire expands and there are multiple cells at fire initially, (at time t = 0). So we will create an auxiliary matrix ‘TIME_OF_FIRE’ of size ‘N’ * ‘M’ to store the minimum time it will take for each cell to catch fire.

Iterate through the given matrix ‘MAT’ [][] and set ‘TIME_OF_FIRE’ [][] for a cell ( ‘i’, ‘j’ ) to 0, if ‘MAT’ [‘i’][‘j’] = 0, (source of fire) because they are on fire from the beginning only.

Fire will expand in four directions(up, down, left, right) from the fired cell and will continue to do so until all the cells are set to fire. A better choice is to use multisource BFS to store all the values of the matrix ‘TIME _OF_FIRE’ [][] for each cell in the matrix.

The steps are as follows:

Initialise a ‘VISITED’ 2D array of type boolean and mark all cells to false.
Those cells which are set to 0 in ‘MAT’[][], push them into a queue and mark them as visited. Also set every cell’s ‘TIME_OF_FIRE’ = ‘TIMER’.
‘TIMER’ acts as clock time.
Multi-source BFS works level by level from each of its source nodes. After each second, source nodes will change. Thus when pushing any cell in the queue the minimum time for this cell to catch fire will be the minimum time taken by its parent + 1. Here the children nodes will be nothing but the adjacent cells.
The next step is to find if the person can reach an escape cell and if yes the minimum time it will take for him to get out of it without being burnt.
To solve this problem, initialise ‘TIMER’ = 0, and do BFS from the initial cell of the person (X, Y).
How to choose, if the next cell will be possible to be visited by the person? To identify this use ‘TIMER’ + 1. If ‘TIMER’ + 1 is less than ‘TIME_OF_FIRE’ of the cell to be visited next, then that cell is possible to be visited safely, otherwise the person will get burnt. So in each iteration insert only those cells in the queue for which ‘TIMER’ + 1 is less than ‘TIME_OF_FIRE’.
To identify if the person has reached escape cells via BFS, there can be these two conditions for escape cells:
1. Either row = 0 or row = ‘N’ - 1:
  1. Either col >= 1 or col <= ‘M’ - 1.
2. Either col = 0 or col = ‘M’ - 1:
  1. Either row >= 1 or row <= ‘N’ - 1.
If the person escapes, then return timer value, else return -1.

Time Complexity

O(N*M), where ‘N’ is the number of rows and ‘M’ is the number of columns in the given matrix.

As there are ‘N’ * ‘M’ cells in the matrix and from each cell we have at most 4 possibilities as each node has 4 edges except the boundary nodes. So through BFS in the worst case, we will be visiting all the nodes/cells. Hence the overall time complexity will be O(N*M).

Space Complexity

O(N*M), where ‘N’ is the number of rows and ‘M’ is the number of columns in the given matrix.

We have used an auxiliary 2D array of size ‘N’ * ‘M’ to store the minimum time for each cell to catch fire, and also we have used another 2D array ‘VISITED’ while performing BFS. Hence overall space complexity is O(N*M).

(100% EXP penalty)

Fire in the cells.

Vivek chaurasia

Interview problems

java solution

import java.util.*;

public class Solution {

public static int fireInTheCells(int[][] mat, int N, int M, int X, int Y) {
int[][] fire = new int[N][M];
Queue<int[]> q = new LinkedList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (mat[i][j] == 0) {
q.offer(new int[]{0, i, j});
fire[i][j] = 0;
} else {
fire[i][j] = -1;
}
}
}

int[] drow = {0, 0, -1, 1};
int[] dcol = {-1, 1, 0, 0};

while (!q.isEmpty()) {
int[] curr = q.poll();
int count = curr[0];
int row = curr[1];
int col = curr[2];

for (int i = 0; i < 4; i++) {
int nrow = row + drow[i];
int ncol = col + dcol[i];

if (nrow >= 0 && ncol >= 0 && nrow < N && ncol < M) {
if (fire[nrow][ncol] == -1) {
q.offer(new int[]{count + 1, nrow, ncol});
fire[nrow][ncol] = count + 1;
}
}
}
}

if (fire[X][Y] == 0 && X != 0 && Y != 0 && X != N - 1 && Y != M - 1) return -1;

Queue<int[]> q2 = new LinkedList<>();
q2.offer(new int[]{0, X, Y});

while (!q2.isEmpty()) {
int[] curr = q2.poll();
int count = curr[0];
int xcor = curr[1];
int ycor = curr[2];

if ((xcor == 0 && ycor != 0 && ycor != M - 1) ||
(xcor == N - 1 && ycor != 0 && ycor != M - 1) ||
(xcor != 0 && ycor == 0 && xcor != N - 1) ||
(xcor != N - 1 && xcor != 0 && ycor == M - 1)) {
return count;
}

for (int i = 0; i < 4; i++) {
int nrow = xcor + drow[i];
int ncol = ycor + dcol[i];

if (nrow >= 0 && ncol >= 0 && nrow < N && ncol < M) {
if (fire[nrow][ncol] > count + 1) {
q2.offer(new int[]{count + 1, nrow, ncol});
}
}
}
}

return -1;
}

public static void main(String[] args) {
int[][] mat = {
{1, 1, 1, 1, 1},
{1, 0, 0, 0, 1},
{1, 0, 1, 0, 1},
{1, 0, 0, 0, 1},
{1, 1, 1, 1, 1}
};

int N = mat.length;
int M = mat[0].length;
int X = 1;
int Y = 1;

int result = fireInTheCells(mat, N, M, X, Y);
System.out.println("Minimum time to escape: " + result);
}
}

24 views

0 replies

1 upvote

Ashis Biswal

Interview problems

python solution

def fireInTheCells(mat, n, m, x, y):

from collections import deque

fire = [[-1 for _ in range(m)] for _ in range(n)]

q = deque()

for i in range(n):

for j in range(m):

if mat[i][j] == 0:

q.append((0, (i, j)))

fire[i][j] = 0

drow = [0, 0, -1, 1]

dcol = [-1, 1, 0, 0]

while q:

row, col = q[0][1]

count = q[0][0]

q.popleft()

for i in range(4):

nrow = drow[i] + row

ncol = dcol[i] + col

if 0 <= nrow < n and 0 <= ncol < m:

if fire[nrow][ncol] == -1:

q.append((count + 1, (nrow, ncol)))

fire[nrow][ncol] = count + 1

if fire[x][y] == 0 and x != 0 and y != 0 and x != n - 1 and y != m - 1:

return -1

q2 = deque()

q2.append((0, (x, y)))

while q2:

xcor, ycor = q2[0][1]

count = q2[0][0]

q2.popleft()

if (xcor == 0 and ycor != 0 and ycor != m - 1) or (xcor == n - 1 and ycor != 0 and ycor != m - 1) or \

(xcor != 0 and ycor == 0 and xcor != n - 1) or (xcor != n - 1 and xcor != 0 and ycor == m - 1):

return count

for i in range(4):

nrow = drow[i] + xcor

ncol = dcol[i] + ycor

if 0 <= nrow < n and 0 <= ncol < m:

if fire[nrow][ncol] > count + 1:

q2.append((count + 1, (nrow, ncol)))

return -1

76 views

0 replies

0 upvotes

Evanston Fx

Interview problems

Invalid testcase

If the escape cell is on fire initially, it's expected that you can't escape from there , but the system expects you to return 0 in that case

54 views

0 replies

0 upvotes

Siddhant

Interview problems

Easy C++ solution

#include <queue>

int fireInTheCells(vector<vector<int>> &mat, int n, int m, int x, int y) {

    vector<vector<int>> fire(n,vector<int>(m,-1));

    queue<pair<int,pair<int,int>>> q;

    for(int i = 0;i<n;i++){

        for(int j = 0;j<m;j++){

            if(mat[i][j] == 0){

                q.push({0,{i,j}});

                fire[i][j] = 0;

            }

        }

    }

    int drow[4] = {0,0,-1,1};

    int dcol[4] = {-1,1,0,0};

    while(!q.empty()){

        int row = q.front().second.first;

        int col = q.front().second.second;

        int count = q.front().first;

        q.pop();

        for(int i = 0;i<4;i++){

            int nrow = drow[i]+row;

            int ncol = dcol[i]+col;

            if (nrow >= 0 && ncol >= 0 && nrow < n && ncol < m) {

                if(fire[nrow][ncol] == -1){

                    q.push({count+1,{nrow,ncol}});

                    fire[nrow][ncol] = count+1;

                }

            }

        }

    }




    if(fire[x][y]==0 && x!=0 && y!=0 && x!=n-1 && y!=m-1) return -1;

    queue<pair<int,pair<int,int>>> q2;

    q2.push({0,{x,y}});

    while(!q2.empty()){

        int xcor = q2.front().second.first;

        int ycor = q2.front().second.second;

        int count = q2.front().first;

        q2.pop();

if((xcor==0 && ycor!=0 && ycor!=m-1) || (xcor==n-1 && ycor!=0 && ycor!=m-1) ||

        (xcor!=0 && ycor==0 && xcor!=n-1) || (xcor!=n-1 && xcor!=0 && ycor==m-1))

        {

            return count;

        }        for(int i = 0;i<4;i++){

            int nrow = drow[i]+xcor;

            int ncol = dcol[i]+ycor;

            if (nrow >= 0 && ncol >= 0 && nrow < n && ncol < m) {

                if(fire[nrow][ncol] > count+1){

                    q2.push({count+1,{nrow,ncol}});

                }

            }         

        }

    }

    return -1;

    // Write your code here.

}

679 views

0 replies

1 upvote

Evanston Fx

Interview problems

Wrong answer coming for test case 9

#include <bits/stdc++.h>

int Xdir[]={1,-1,0,0};

int Ydir[]={0,0,1,-1};

bool isValid(int i,int j,int n,int m){

return i>=0 && i<n && j>=0 && j<m;

}

bool reachedEdge(int i,int j,int n,int m){

return (i==0 && (j!=m-1 || j!=0)) ||

(i==n-1 && (j!=m-1 || j!=0)) ||

(j==0 && (i!=n-1 || i!=0)) ||

(j==m-1 && (i!=n-1 || i!=0)) ;

}

void bfs(vector<vector<int>> &mat,int i,int j,int n,int m,vector<vector<int>> &time_to_burn){

queue<pair<int,int>> q;

q.push(make_pair(i,j));

vector<vector<bool>> vis(n,vector<bool>(m,false));

vis[i][j]=true;

time_to_burn[i][j]=0;

while(!q.empty()){

pair<int,int> front=q.front();

q.pop();

int x=front.first;

int y=front.second;

for(int i=0;i<4;i++){

int newX=x+Xdir[i];

int newY=y+Ydir[i];

if(isValid(newX,newY,n,m) && !vis[newX][newY]){

time_to_burn[newX][newY]=min(time_to_burn[newX][newY],1+time_to_burn[x][y]);

vis[newX][newY]=true;

q.push(make_pair(newX,newY));

}

return;

}

int bfs2(vector<vector<int>>& time_to_burn,int i,int j,int n,int m, vector<vector<int>> & time_to_reach){

queue<pair<int,int>> q;

q.push(make_pair(i,j));

vector<vector<bool>> vis(n,vector<bool>(m,false));

vis[i][j]=true;

time_to_reach[i][j]=0;

while(!q.empty()){

pair<int,int> front=q.front();

q.pop();

int x=front.first;

int y=front.second;

if(reachedEdge(x, y, n, m)) {

if(time_to_reach[x][y]<time_to_burn[x][y]){

return time_to_reach[x][y];

}

for(int i=0;i<4;i++){

int newX=x+Xdir[i];

int newY=y+Ydir[i];

if(isValid(newX,newY,n,m) && !vis[newX][newY]){

time_to_reach[newX][newY]=time_to_reach[x][y]+1;

vis[newX][newY]=true;

q.push(make_pair(newX,newY));

}

return -1;

}

int fireInTheCells(vector<vector<int>> &mat, int n, int m, int x, int y) {

vector<vector<int>> time_to_burn(n,vector<int>(m,INT_MAX));

for(int i=0;i<n;i++){

for(int j=0;j<m;j++){

if(mat[i][j]==0){

bfs(mat,i,j,n,m,time_to_burn);

}

vector<vector<int>> time_to_reach(n,vector<int>(m,0));

return bfs2(time_to_burn,x,y,n,m,time_to_reach);

}

87 views

0 replies

0 upvotes

Codestudio

Interview problems

Discussion thread on Interview Problem | Fire in the cells.

Hey everyone, creating this thread to discuss the interview problem - Fire in the cells..

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Fire in the cells.

457 views

6 replies

0 upvotes

Console