python - 二维数组中 1 的岛的最大面积

Question

question阅读以下内容:

Given a non-empty 2D array grid of 0's and 1's, an island is a groupof 1's (representing land) connected 4-directionally (horizontal orvertical.) You may assume all four edges of the grid are surrounded bywater.

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

class Solution:

    def maxAreaOfIsland( self, grid: List[List[int]]) -> int:
        a = len(grid)
    
        
        for x in range(0, a):
            b = len(grid[x])
            for y in range(0 , b):
                if grid[x][y] == "1":
                    self.dfs(grid , x , y)
        
        return count
                    
    def dfs(self,grid, i, j):
        count = 0
        
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == "0" or grid[i][j] == "2":
            return 
        
        grid[i][j] = "2"
        count += 1
    
        self.dfs(grid , i-1 , j)
        self.dfs(grid , i+1, j)
        self.dfs(grid, i , j-1)
        self.dfs(grid , i , j+1)

我正在尝试使用深度优先搜索方法来寻找邻居。但是，我不知道如何在找到“1”以及输出总计数时正确增加计数。

Answer 1

您可以通过为陆地上的位置构建一个坐标(集合)字典来在没有递归的情况下做到这一点。然后为连接到右侧或下方其他土地位置的每个土地位置合并这些集合。结果将是所有连接位置的一组通用位置。这些集合中最大的一个的长度将是最大岛屿的面积:

def maxIsland(grid):
    rows,cols = len(grid),len(grid[0])
    land      = { (r,c):{(r,c)} for r in range(rows) for c in range(cols) if grid[r][c] }
    for (r,c) in list(land):
        for nr,nc in [(r+1,c),(r,c+1)]:            # Positions below/right 
            if (nr,nc) not in land:  continue      # connecting land 
            if land[r,c] is land[nr,nc]: continue  # skip already merged
            land[r,c].update(land[nr,nc])          # Merge set of positions 
            for (lr,lc) in land[nr,nc]: 
                land[lr,lc] = land[r,c]            # Propagate merged set to all
    return max(map(len,land.values()))             # return size of largest set

输出:

world = [ "0000000000000",
          "0111000000111",
          "0101110000111",
          "0100111100111",
          "0100000100000",
          "0101001110000",
          "0111001110000" ]
world = [ list(map(int,row)) for row in world ]

print( maxIsland(world) ) # 25

对于更基本的方法，您可以从一组陆地坐标开始工作，并在测量岛屿大小的同时逐步取出连接到岛屿的坐标。扩大一个陆地坐标，增加未知的邻居，扩大岛屿新增位置即可形成岛屿:

def maxIsland(grid):
    rows,cols = len(grid),len(grid[0])
    land      = { (r,c) for r in range(rows) for c in range(cols) if grid[r][c] }
    result    = 0
    while land:                    # find new islands in uncharted land
        island    = [land.pop()]           # pick a coordinate to expand into an island
        expanding = 0                      # will expand coordinates added by expansion
        while expanding<len(island):
            r,c = island[expanding]                         # expand added coordinate 
            neighbours = {(r+1,c),(r-1,c),(r,c+1),(r,c-1)}  # candidate coordinates
            island    += list(land & neighbours)            # add uncharted land to island
            land      -= neighbours                         # remove from uncharted land
            expanding += 1                                  
        result = max(result,len(island))   # track largest island
    return result

注意:这将比第一个在大网格上运行得快得多