0695. Max Area of Island (M)

题目

You are given an m x n binary matrix grid. An island is a group of 1‘s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Example 1:

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] is either 0 or 1.

题意

给定一个矩阵，0代表水，1代表岛，一个岛与垂直和水平方向相邻的岛组成一个更大的岛，求最大的岛的面积。

思路

直接DFS找每一个岛区域的大小即可。

代码实现

Java

class Solution {
    private int m, n;
    private int[] xShift = {-1, 0, 1, 0};
    private int[] yShift = {0, -1, 0, 1};
    public int maxAreaOfIsland(int[][] grid) {
        int ans = 0;
        m = grid.length;
        n = grid[0].length;
        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]) {
                    ans = Math.max(ans, dfs(grid, x, y, visited));
                }
            }
        }
        return ans;
    }
    private int dfs(int[][] grid, int x, int y, boolean[][] visited) {
        int cnt = 1;
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + xShift[i];
            int ny = y + yShift[i];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1 && !visited[nx][ny]) {
                cnt += dfs(grid, nx, ny, visited);
            }
        }
        return cnt;
    }
}