# Infected computers

• You maintain a square grid of computers where each one is only connected to the neighboring computers that are directly adjacent to it, i.e. vertically or horizontally. You have discovered, to your chagrin, that several of your computers have been infected with an alien virus. Your healthy computers become infected if two or more of their adjacent neighbors are infected. Which of your computers end up as infected after the infection has spread as far as it can?

Input definition

An input file will contain an n by n square grid of numbers consisting of 0s and 1s. Each of the n rows will contain exactly n binary digits and no whitespace between 0s and 1s. In the grid, 1s represent infected computers and 0s represent healthy ones. The grid is always square and n can range from 7 to 9, inclusive.

Output definition

Your output should contain an n by n square grid of numbers consisting of 0s and 1s, representing the final state of the infection. As before, 1s shall represent infected computers and 0s shall represent healthy ones.

Example input

``````00000000
01010000
00010000
01001000
00010010
00001000
00001001
01000000
``````

Example output

``````00000000
01111111
01111111
01111111
01111111
01111111
01111111
01111111
``````

• One approach would be

For each element in the grid
If value == 0, move to next element // skip clean machines
if value == 1, call DoInfect(row, col) method // see if this can infect its neighbors

DoInfect(row, col)
Call FindNeighbors(row, col) // get a list of the neighbors
For each neighbor in list of neighbors
if neighbor.value == 1, move to next neighbor // ignore if already infected
if neighbor.value == 0, call FindNeighbors(neighbor.row, neighbor.col)
// see if this clean computer has more than 1 infected neighbor
For each neighbor.neighbor
//make sure not to count the original infected computer
if (value == 1 && neighbor.neighbor != self)
neighbor.value = 1 //two neighbors are infected so infect it
//if this is a neighbor we had already covered in original loop then recursively infect its neighbors
if (neighbor.row < row || neighbor.col < col)
DoInfect(neighbor.row, neighbor.col)

FindNeighbors(row, col) //find neighbors within the bounds of the array
if (row > 0)
if (col > 0)
if (row + 1< input.rows.Length)
if (col + 1< input.cols.Length)

• ``````package graph;

// used arrays for simmplicity, you need to read file and convert input to array
public class InfectedComputers {
public static void main(String args[]) {
// using DFS
int M[][]=
{ {0,0,0,0,0,0,0,0},
{0,1,0,1,0,0,0,0},
{0,0,0,1,0,0,0,0},
{0,1,0,0,1,0,0,0},
{0,0,0,1,0,0,1,0},
{0,0,0,0,1,0,0,0},
{0,0,0,0,1,0,0,1},
{0,1,0,0,0,0,0,0}
};

// to maintain visited computers which are not infected i.e. 0
boolean visited[][] = new boolean[M.length][M[0].length];

// visit all healthy computers
for(int i = 0; i < M.length; i++) {
for(int j = 0; j < M[0].length; j++) {
// if computer is infected do nothing
if(M[i][j] == 1) {
continue;
} else {
// if computer is not infected do DFS to check if it can be infected
dfs(M, i, j, visited);
}
}
}

// print result
for(int i = 0; i < M.length; i++) {
for(int j = 0; j < M[0].length; j++) {
System.out.print(M[i][j]);
}
System.out.println();
}

}

// method to check whether computer is infected
public static boolean isInfected(int[][] mat, int row, int col) {
return row >= 0 && col >= 0 && row < mat.length
&& col < mat[0].length && mat[row][col] == 1;
}

// using DFS
public static void dfs(int[][] mat, int row, int col, boolean visited[][]) {
// positions (0,-1), (0,1), (1,0) and (-1,0) which represents vertical and horizontal adjacent comps
int r[] = {0, 0, 1, -1};
int c[] = {-1, 1, 0, 0};

// constant to store adjacent infected comps
int infectCnt = 0;
// traverse all up, down, left, right
for(int i = 0; i < 4; ++i) {
if(isInfected(mat, row+r[i], col+c[i])) {
infectCnt++;
}
}

// if more than 2 neighbors infected then infect current comp and do DFS on all its adjacent comps
if(infectCnt >= 2) {
mat[row][col] = 1;
visited[row][col] = true;
for(int i = 0; i < 4; ++i) {
int newRow = row+r[i];
int newCol = col+c[i];
if(newRow >= 0 && newCol >= 0 && newRow < mat.length
&& newCol < mat[0].length && mat[newRow][newCol] == 0 && !visited[newRow][newCol])
dfs(mat, newRow, newCol, visited);
}
}
}
}``````

• @ajay52
Thanks a lot!!! But why we have to record visited computers?
The following is my C++ version based on your idea. I don't record visited computers but the answer is still correct.

``````//whether computer(x,y) is infected or not
bool isInfected(int x, int y, int n, std::vector<std::vector<int>> &computers){
return x>=0 && y>=0 && x<n && y<n && computers[x][y]==1;
}

void DFS(int x, int y, int &n, std::vector<std::vector<int>> &computers){
if(x<0 || y<0 || x>=n || y>=n || computers[x][y]==1)
return;

//four directions
std::vector<int> row = {-1,1,0,0};
std::vector<int> col = {0,0,-1,1};

//number of infected computers which are adjacent to computer (x,y)
int infectCount = 0;
for(int i=0; i<4; i++){
if(isInfected(x+row[i],y+col[i],n,computers))
infectCount++;
}

if(infectCount >= 2){
computers[x][y] = 1;
for(int i=0; i<4; i++)
DFS(x+row[i],y+col[i],n,computers);
}
}

void InfectComputer(std::vector<std::vector<int>> &computers){
int n = computers.size();
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(computers[i][j] == 0)
DFS(i,j,n,computers);
}
}
}

int main()
{
std::vector<std::vector<int>> computers = {{0,0,0,0,0,0,0,0},
{0,1,0,1,0,0,0,0},
{0,0,0,1,0,0,0,0},
{0,1,0,0,1,0,0,0},
{0,0,0,1,0,0,1,0},
{0,0,0,0,1,0,0,0},
{0,0,0,0,1,0,0,1},
{0,1,0,0,0,0,0,0}};
for(auto row : computers){
for(auto col : row)
std::cout << col;
std::cout << std::endl;
}
std::cout << "----------------------------------------" << std::endl;
InfectComputer(computers);

//print result
for(auto row : computers){
for(auto col : row)
std::cout << col;
std::cout << std::endl;
}
return 0;
}
``````

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