Java Solution (Accepted)


  • 0

    I didn't take part in the competition. Just for fun. :-P

    class Solution {
        class Virus {
            int row, col;
            int cellsCovered = 0;
            int wallsNeeded = 0;
            boolean contained = false;
            ArrayList<Virus> cellsCanInfect = new ArrayList<>();
            Virus(int r, int c) {
                row = r;
                col = c;
            }
            void addCellCanInfect(int r, int c) {
                cellsCanInfect.add(new Virus(r,c));
            }
        }
        
        public int containVirus(int[][] grid) {
            int width = grid[0].length;
            int height = grid.length;
            
            LinkedList<Virus> containedViruses = new LinkedList<>();
            ArrayList<Virus> uncontainedViruses = new ArrayList<>();
            findViruses(grid, uncontainedViruses);
            
            int numContainedVirusCells = 0;
            int numUncontainedVirusCells = 0;
            int worldSize = width*height;
            
            while(!uncontainedViruses.isEmpty() && numContainedVirusCells + numUncontainedVirusCells != worldSize) {
                numUncontainedVirusCells = growViruses(grid,uncontainedViruses);
                containedViruses.add(removeBiggestVirus(uncontainedViruses, grid));
                int newCellsContained = containedViruses.getLast().cellsCovered;
                numContainedVirusCells += newCellsContained;
                numUncontainedVirusCells -= newCellsContained;
                removeJoinedViruses(grid,uncontainedViruses);
            }        
            int walls = 0;
            for(Virus v : containedViruses) {
                walls += v.wallsNeeded;
            }
            return walls;
        }
        
        private boolean invalidCell(int i, int j, int[][] grid) {
            return i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == 8; // Contained virus marked with 8
        }
     
        private void findViruses(int[][] grid, ArrayList<Virus> viruses) {
            boolean[][] visited = new boolean[grid.length][grid[0].length];
            for(int i=0; i<grid.length; i++) {
                for(int j=0; j<grid[0].length; j++) {
                    if(!visited[i][j] && grid[i][j] == 1) {
                        Virus newVirus = new Virus(i,j);
                        viruses.add(newVirus);
                        markVirusCells(grid,i,j,visited);
                    }
                }
            }
        }
        
        private void markVirusCells(int[][] grid, int i, int j, boolean[][] visited) {
            if(invalidCell(i,j,grid) || visited[i][j] || grid[i][j] == 0) return;
            visited[i][j] = true;
            markVirusCells(grid,i+1,j,visited);
            markVirusCells(grid,i-1,j,visited);
            markVirusCells(grid,i,j+1,visited);
            markVirusCells(grid,i,j-1,visited);
        }
    
        private int growViruses(int[][] grid, ArrayList<Virus> viruses) {
            int uncontainedVirusCells = 0;
            for(Virus v : viruses) {
                for(Virus c : v.cellsCanInfect) {
                    grid[c.row][c.col] = 1;
                }
                v.cellsCanInfect.clear();
            }
            for(Virus v : viruses) {
                v.cellsCovered = 0;
                v.wallsNeeded = 0;
                visitVirus(grid,v.row,v.col,v,new boolean[grid.length][grid[0].length]);
                uncontainedVirusCells += v.cellsCovered;
            }
            return uncontainedVirusCells;        
        }
        
        private void visitVirus(int[][] grid, int i, int j, Virus v, boolean[][] visited) {
            if (invalidCell(i,j,grid)) return;
            if(!visited[i][j]) {
                visited[i][j] = true;
                if(grid[i][j] == 0) {
                    v.addCellCanInfect(i,j);
                } else {
                    v.cellsCovered++;
                    visitVirus(grid,i+1,j,v,visited);
                    visitVirus(grid,i,j+1,v,visited);
                    visitVirus(grid,i-1,j,v,visited);
                    visitVirus(grid,i,j-1,v,visited);            
                }
            }
            if(grid[i][j] == 0) {
                v.wallsNeeded++;
            }
        }
            
        private Virus removeBiggestVirus(ArrayList<Virus> viruses, int[][] grid) {
            int biggestVirusIndex = 0;
            int biggestVirusSize = 0;
            for(int i=0; i<viruses.size(); i++) {
                Virus v = viruses.get(i);
                int growthSize = v.cellsCanInfect.size();
                if(growthSize > biggestVirusSize) {
                    biggestVirusIndex = i;
                    biggestVirusSize = growthSize;
                }
            }
            containVirus(grid,viruses.get(biggestVirusIndex));
            return viruses.remove(biggestVirusIndex);
        }
    
        private void containVirus(int[][] grid, Virus v) {
            containVirusHelper(grid,v.row,v.col);
            v.contained = true;
        }
        
        private void containVirusHelper(int[][] grid,int i, int j) {
            if(invalidCell(i,j,grid)) return;
            if(grid[i][j] == 1) {
                grid[i][j] = 8;
                containVirusHelper(grid,i,j+1);
                containVirusHelper(grid,i+1,j);
                containVirusHelper(grid,i-1,j);
                containVirusHelper(grid,i,j-1);
            }
        }
        
        // Remove viruses that merged into one
        private void removeJoinedViruses(int[][] grid, List<Virus> viruses) {
            Iterator<Virus> i = viruses.iterator();
            while(i.hasNext()) {
                Virus v = i.next();
                if(grid[v.row][v.col] == 8) {
                    i.remove();
                }
            }
        }
    }
    

Log in to reply
 

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