python - 岛屿的最大面积

Question

我参加了一个编码竞赛，我非常接近解决以下问题，但由于某种原因我的代码无法运行 =(

这是问题的链接: https://leetcode.com/contest/leetcode-weekly-contest-53/problems/max-area-of-island/

我的解决方案:

class Solution(object):
 def maxAreaOfIsland(self, grid):
    """
    :type grid: List[List[int]]
    :rtype: int
    """
    self.longest = 0
    self.count = 0
    row = len(grid)
    col = len(grid[0])
    for i in range(row):
        for j in range(col):
            if grid[i][j] == 1:
                self.count += 1
                current = 1
                self.countIsland(i, j, current, grid)
    return self.longest
  def countIsland(self, k, z, current, grid):
    print(str(k) + "," + str(z) + "=" + str(current))
    grid[k][z] = -1
    if k > 0 and grid[k-1][z] == 1:
           return self.countIsland(k-1, z, current+1, grid)
    if k < (len(grid)-1) and grid[k+1][z] == 1:
           return self.countIsland(k+1, z, current+1, grid)
    if z > 0 and grid[k][z - 1] == 1:
           return self.countIsland(k, z-1, current+1, grid)
    if z < (len(grid[0])-1) and grid[k][z+1] == 1:
          return self.countIsland(k, z+1, current+1, grid)
    self.longest = max(self.longest, current)
    return current  

我差了 1，我得到 5 而不是 6。如果您尝试在 IDE 中运行它，我的打印语句将显示对于递归的最后一次调用，当前值正在重新初始化，即不是我想要的。有什么想法吗？

谢谢!

Answer 1

基本方法很直观。我们使用 DFS 在每个可能的位置扩展岛屿。当访问一个岛细胞时，我们将其“下沉”。下面是我的 Java 实现，并通过了 Leetcode 上的所有测试。

class Solution {
    private static final int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    public int maxAreaOfIsland(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    res = Math.max(res, dfs(grid, i, j));
                }
            }
        }
        return res;
    }

    private int dfs(int[][] grid, int x, int y) {
        if (grid[x][y] == 0) {
            return 0;
        }

        grid[x][y] = 0;
        int cnt = 1;
        for (int[] dir : dirs) {
            int nx = x + dir[0], ny = y + dir[1];
            if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length && grid[nx][ny] == 1) {
                cnt += dfs(grid, nx, ny);
            }
        }
        return cnt;
    }
}