Java DFS beats 88% as of 10/21/18
``` class Solution { static int[] dir = {-1, 0, 1, 0, -1}; public int containVirus(int[][] grid) {     if (grid == null || grid.length == 0 || grid[0].length ==
```
class Solution {
    
    static int[] dir = {-1, 0, 1, 0, -1};
    
    public int containVirus(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int m = grid.length, n = grid[0].length, target = 0, walls = 0;
        for (int[] row: grid) {
            for (int e: row) {
                if (e == 1) target++;
            }
        }
        while (target > 0) {
            List<Set<Integer>> zeroList = new ArrayList<>();
            List<List<int[]>> oneList = new ArrayList<>();
            boolean[][] visited = new boolean[m][n];
            for (int x = 0; x < m; x++) {
                for (int y = 0; y < n; y++) {
                    if (grid[x][y] == 1 && !visited[x][y]) {
                        Set<Integer> zero = new HashSet<>();
                        List<int[]> one = new ArrayList<>();
                        nav(x, y, grid, visited, zero, one);
                        zeroList.add(zero);
                        oneList.add(one);
                    }
                }
            }
            int index = -1, max = -1;
            for (int i = 0; i < zeroList.size(); i++) {
                Set<Integer> zeros = zeroList.get(i);
                if (zeros.size() > max) {
                    max = zeros.size();
                    index = i;
                }
            }
            List<int[]> ones = oneList.get(index);
            for (int[] one: ones) {
                grid[one[0]][one[1]] = -1;
                for (int i = 0; i < 4; i++) {
                    int nx = one[0] + dir[i], ny = one[1] + dir[i + 1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                        walls++;
                    }
                }
            }
            target -= ones.size();
            Set<Integer> merged = new HashSet<>();
            for (int i = 0; i < zeroList.size(); i++) {
                if (i == index) continue;
                merged.addAll(zeroList.get(i));
            }
            for (int z: merged) {
                int x = z / n, y = z % n;
                grid[x][y] = 1;
            }
            target += merged.size();
        }
        return walls;
    }
    
    private void nav(int x, int y, int[][] grid, boolean[][] visited, Set<Integer> zeros, List<int[]> ones) {
        int m = grid.length, n = grid[0].length;
        visited[x][y] = true;
        ones.add(new int[] {x, y});
        for (int i = 0; i < 4; i++) {
            int nextX = x + dir[i], nextY = y + dir[i + 1];
            if (nextX < 0 || nextX >= m ||
                nextY < 0 || nextY >= n || visited[nextX][nextY]) continue;
            if (grid[nextX][nextY] == 0) {
                zeros.add(nextX * n + nextY);
            } else if (grid[nextX][nextY] == 1) {
                nav(nextX, nextY, grid, visited, zeros, ones);
            }
        }
    }
}
```

[]