最大面積

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