695. Max Area of Island

[Woodyiiiiiii]

典型的二维数组遍历问题。有DFS和BFS两种方法。写下这个题解用作记录，两种方法都要掌握。

有时候DFS会超时，就要试试BFS，反之也是。比如题目1091. Shortest Path in Binary Matrix。

DFS：

class Solution {
    int tmpSum, maxArea = 0;
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        boolean[][] v = new boolean[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (!v[i][j] && grid[i][j] == 1) {
                    tmpSum = 0;
                    dfs(grid, v, i, j);
                }
                v[i][j] = true;
            }
        }
        return maxArea;
    }
    public void dfs(int[][] grid, boolean[][] v, int i, int j) {
        v[i][j] = true;
        ++tmpSum;
        maxArea = Math.max(maxArea, tmpSum);
        if (j + 1 < grid[0].length && grid[i][j + 1] == 1 && !v[i][j + 1]) {
            dfs(grid, v, i, j + 1);
        }
        if (i + 1 < grid.length && grid[i + 1][j] == 1 && !v[i + 1][j]) {
            dfs(grid, v, i + 1, j);
        }
        if (j - 1 >= 0 && grid[i][j - 1] == 1 && !v[i][j - 1]) {
            dfs(grid, v, i, j - 1);
        }
        if (i - 1 >= 0 && grid[i - 1][j] == 1 && !v[i - 1][j]) {
            dfs(grid, v, i - 1, j);
        }
    }
}

BFS：

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        
        int m = grid.length;
        int n = grid[0].length;
        
        final int[][] xy = new int[][]{{-1,0},{0,-1},{1,0},{0,1}};
        boolean[][] v = new boolean[m][n];
        int res = 0;
        
        for (int i = 0; i < m; ++i){
            for (int j = 0; j < n; ++j) {
                if (v[i][j] || grid[i][j] == 0) {
                    continue;
                }
                
                res = Math.max(res, BFS(grid, v, xy, i, j));
            }
        }
        
        return res;
        
    }
    
    private int BFS(int[][] grid, boolean[][] v, final int[][] xy, int o1, int o2) {
        
        Deque<int[]> queue = new LinkedList<>();
        queue.add(new int[]{o1, o2});
        v[o1][o2] = true;
        int res = 0;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int t = 0; t < size; ++t) {
                
                int[] p = queue.poll();
                int i = p[0];
                int j = p[1];
                
                for (int k = 0; k < xy.length; ++k) {
                    int ii = i + xy[k][0];
                    int jj = j + xy[k][1];
                    if (ii >= 0 && ii < grid.length && jj >= 0 && jj < grid[0].length && !v[ii][jj] && grid[ii][jj] != 0) {
                        v[ii][jj] = true;
                        queue.add(new int[]{ii, jj});
                    } 
                }
                
            }
            res += size;
        }
        
        return res;
        
    }
}

类似的题目还有参考资料的No.329。

---

参考资料：

• https://leetcode.com/problems/max-area-of-island/
• 1091. Shortest Path in Binary Matrix
• 329. Longest Increasing Path in a Matrix