最大面积

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中运行它，我的print语句将表明，递归的最后一次调用中，当前值正在重新初始化这不是我想要的。任何想法为什么？

谢谢！

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; 
    } 
}