题目描述

Given a non-empty 2D array grid of 0's and 1's, 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.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:

[[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]]

Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.

Example 2:

[[0,0,0,0,0,0,0,0]]

Given the above grid, return 0.

Note: The length of each dimension in the given grid does not exceed 50.

解法一

思路

这题就是典型的DFS啦,遍历矩阵,每当碰到1的时候就开始DFS,DFS每次碰到1就增加计数,然后把这个位置的值置为0,DFS最后返回计数值,然后每次DFS返回值的最大值就是结果了。

有两点要注意的:

  • 为了避免DFS重复计数,对于访问过的1,马上置为0即可。
  • 注意到DFS是一个递归的过程,所以每一层只需要返回本身的计数(1)以及其子递归返回的计数(由此处出发DFS遍历到的1的个数)的和就可以了。

Python

class Solution:
    def maxAreaOfIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        steps = ((-1, 0), (1, 0), (0, -1), (0, 1))

        def dfs(grid, x, y, m, n):
            if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] == 0:
                return 0
            count = 1
            grid[x][y] = 0
            for i, j in steps:
                count += dfs(grid, x + i, y + j, m, n)
            return count

        result = 0
        m = len(grid)
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    result = max(result, dfs(grid, i, j, m, n))
        return result

Java

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        class Utils {
            int[][] steps = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

            int dfs(int[][] grid, int x, int y, int m, int n) {
                if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0) {
                    return 0;
                }
                int count = 1;
                grid[x][y] = 0;
                for (int[] step : steps) {
                    count += dfs(grid, x + step[0], y + step[1], m, n);
                }
                return count;
            }
        }
        int result = 0;
        int m = grid.length;
        int n = grid[0].length;
        Utils utils = new Utils();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    result = Math.max(result, utils.dfs(grid, i, j, m, n));
                }
            }
        }
        return result;
    }
}

C++

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>> &grid) {
        class Utils {
        public:
            int steps[4][2] = {{-1, 0},
                {1,  0},
                {0,  -1},
                {0,  1}
            };

            int dfs(vector<vector<int>> &grid, int x, int y, int m, int n) {
                if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0) {
                    return 0;
                }
                int count = 1;
                grid[x][y] = 0;
                for (auto &step : steps) {
                    count += dfs(grid, x + step[0], y + step[1], m, n);
                }
                return count;
            }
        };
        int result = 0;
        int m = grid.size();
        int n = grid[0].size();
        Utils utils;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    result = max(result, utils.dfs(grid, i, j, m, n));
                }
            }
        }
        return result;
    }
};