Infected computers


  • 1
    L

    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
    

  • 0
    V

    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)
    neighborList.add(row-1, col)
    if (col > 0)
    neighborList.add(row, col - 1)
    if (row + 1< input.rows.Length)
    neighborList.add(row+1, col)
    if (col + 1< input.cols.Length)
    neighborList.add(row, col + 1)


  • 2
    A
    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);
    			}
    		}
    	}
    }

  • 0
    L

    @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;
    }
    

Log in to reply
 

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