Poison

695. Max Area of Island

发表于
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    private static final int[][] DIRECTIONS = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;

        int maxArea = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int area = dfs(grid, m, n, i, j);
                    maxArea = Math.max(maxArea, area);
                }
            }
        }

        return maxArea;
    }

    private int dfs(int[][] grid, int m, int n, int i, int j) {
        int area = 1;
        
        grid[i][j] = 0;
        for (int[] direction : DIRECTIONS) {
            int nextI = i + direction[0];
            int nextJ = j + direction[1];
            if (nextI >= 0 && nextI < m && nextJ >= 0 && nextJ < n && grid[nextI][nextJ] == 1) {
                area += dfs(grid, m, n, nextI, nextJ);
            }
        }

        return area;
    }
}
BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    private static final int[][] DIRECTIONS = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;

        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int area = bfsMark(grid, i, j);
                    maxArea = Math.max(maxArea, area);
                }
            }
        }

        return maxArea;
    }

    private int bfsMark(int[][] grid, int i, int j) {
        int m = grid.length, n = grid[0].length;
        int area = 0;

        Queue<int[]> queue = new LinkedList<>();
        grid[i][j] = 0;
        queue.offer(new int[]{i, j});
        while (!queue.isEmpty()) {
            area += queue.size();
            for (int k = queue.size(); k > 0; k--) {
                int[] cell = queue.poll();
                for (int[] direction : DIRECTIONS) {
                    int nextI = cell[0] + direction[0], nextJ = cell[1] + direction[1];
                    if (nextI >= 0 && nextI < m && nextJ >= 0 && nextJ < n && grid[nextI][nextJ] == 1) {
                        grid[nextI][nextJ] = 0;
                        queue.offer(new int[]{nextI, nextJ});
                    }
                }
            }
        }

        return area;
    }
}
Reference

695. Max Area of Island