# There is a matrix which can have 3 values 0,1,2.0 ->blocked cell,2 ->virus on the cell,1 -> effected by the virus

• represents virus on the cell , 1 represents a cell which can be effected by the virus . Neighbouring cell's having value 1 infected by the virus and converts into 2 .After this recently converted cell's will infect all the cells having value as 1 and changed into 2 . This process will go on until we have reach a situation such that no further conversion can took place.

We are considering all the 8 neighbours . Eg - if the cell in the consideration is i,j then the neighbours will be (i , j-1) , (i-1 , j-1) , (i-1 , j) , (i-1 , j+1) , (i , j+1) , (i+1 , j+1) , (i+1 , j) , (i+1 , j-1) .

So, we need to find out the number of chances it will take to convert the matrix to the above mentioned location .

It would be more good if we can print all the intermediate state .

• I guess this is a duplicate of this post. I assume that the virus will be placed initially from a cell that has value 1, then we just need to do a BFS from that place, and print the intermediate state at every level.

• I am not very clear how to implement it in code, could you please help to provide some sample codes? thanks a lot.

• Is this something you are looking for? I don't know if I implemented it correct as per requirements. It seems DFS have to be applied here. How can we use BFS here?

``````package Amazon;

public class VirusMatrix {

private void printMatrix(int[][] matrix, final int ROWS, final int COLS) {
for(int row=0; row<ROWS; row++) {
for(int col=0; col<COLS; col++) {
System.out.print(matrix[row][col] + " , ");
}
System.out.println("");
}

System.out.println("************ \n");

}

private void spreadVirus(int[][] matrix, final int ROWS, final int COLS, int virus_row, int virus_col) {
matrix[virus_row][virus_col] = 2;

for (int row = virus_row - 1; row <= virus_row + 1; row++) {
for (int col = virus_col - 1; col <= virus_col + 1; col++) {
if (row >= 0 && row < ROWS && col >= 0 && col < COLS && ! (row == virus_row && col == virus_col)) {
if (matrix[row][col] == 1) {
}
}
}
}

printMatrix(matrix, ROWS, COLS);
}

public static void main(String[] args) {
VirusMatrix vm = new VirusMatrix();
int matrix[][] = { { 1, 2, 0, 1 },
{ 0, 1, 1, 2 },
{ 2, 2, 0, 0 },
{ 0, 1, 0, 1 } };

}

}

``````

• @ramanpreetSinghKhinda nice and clear. a possible improvement is to mark the already spreaded cells (with value 2) as DONE, so they don't need to be processed again.

• My BFS solution. `count` starts at `2` and every time the search moves one level deeper, `count` is incremented and the board state is printed out. I use the board itself to track each level of infection. If you don't want to use the board, you can extend the `Pair` class with a count value. Alternatively you can post process the board to replace every value `>2` with `2`.
If there are any grid squares that cannot be infected (surrounded with 0s) you can check the board at the end for any 1s left and print something else accordingly.

``````public class VirusInfect {

class Pair {
int i, j;
Pair(int ii, int jj) {i=ii;j=jj;}
}

public void infect(int S[][], int i, int j, int count, Queue<Pair> q) {
if (i < 0 || j < 0 || i == S.length || j == S[0].length || S[i][j] != 1) {
return;
}
S[i][j] = count;
}

@Test
public void solve() {

int S[][] = new int[][]{
{2, 1, 1},
{1, 1, 0},
{0, 0, 1}};

int count = 2;

for (int i = 0; i < S.length; i++) {
for (int j = 0; j < S[0].length; j++) {
if (S[i][j] == count) {
}
}
}

do {

Pair p = queue.poll();
if (S[p.i][p.j] > count) {
printBoard(S, ++count);
}
infect(S, p.i + 1, p.j, count + 1, queue);
infect(S, p.i - 1, p.j, count + 1, queue);
infect(S, p.i, p.j + 1, count + 1, queue);
infect(S, p.i, p.j - 1, count + 1, queue);
infect(S, p.i + 1, p.j - 1, count + 1, queue);
infect(S, p.i - 1, p.j - 1, count + 1, queue);
infect(S, p.i + 1, p.j + 1, count + 1, queue);
infect(S, p.i - 1, p.j + 1, count + 1, queue);

} while (!queue.isEmpty());

System.out.println("Total seconds elapsed : " + (count-2));
}

void printBoard(int S[][], int count) {
System.out.println("Level " + (count - 2) + ":");
for (int i = 0; i < S.length; i++) {
for (int j = 0; j < S[0].length; j++) {
System.out.print(S[i][j] + " ");
}
System.out.println();
}
}
}
``````

Output:

``````Level 1:
2 3 1
3 3 0
0 0 1
Level 2:
2 3 4
3 3 0
0 0 4
Total seconds elapsed : 2
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.