2D数组中由1组成的最大岛屿面积

Question

题目描述如下：

给定一个非空的二维数组grid，由0和1组成，岛屿是一组1（表示陆地），在4个方向上（水平或垂直）连通。您可以假设网格的四个边都被水包围。

在给定的2D数组中找到最大岛屿的面积。（如果没有岛屿，则最大面积为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"时如何正确增加计数以及输出总计数的方法让我无从下手。

- user12852585

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

注意：对于大型网格，这个运行速度比第一个要快得多。

- Alain T.

Answer 2

在最后一种方法中，使用坐标（集合）字典来表示陆地上的位置。如果我发现最大集合的大小由8个相连的坐标对组成，那么我该如何仅获取前五个相连的坐标及其对应的矩阵值？ 为了获取与最大岛屿上相连坐标相关联的矩阵值，我尝试了以下方法。

        data = list(land.items())
        data_1= sorted(data) # sort the list of coordinate pairs for length
        an_array = np.array(data_1)
        islands= max(map(len,land.values()))
        if islands >1:
            arr = an_array[islands-1][1]
            for i in arr:
                listx.append(i[0])
                listy.append(i[1])
            
            for ix,iy,zip(range(len(listx)),range(len(listx)),listx,listy):
                    matrix=grid[list1[i]][list2[i]]
                    print "Coordinate X",listx[ix],"Coordinate Y ",listy[iy],"Values in the matrix" ,matrix
                    

但是我无法获取矩阵中的前五个相连坐标及其对应的值。

请注意：我使用的是不同数值的矩阵。

- Domenico Impiombato

Answer 3

为了能够在递归函数中增加计数，它应该是一个类变量或全局变量。您还尝试每次进入dfs时将其重置为0，这是不好的，因为您的dfs函数将调用自身并将该计数重置为0。您的基本想法很好，您将已访问的部分标记为“2”。唯一可以改变的是您对边缘所做的检查。问题说明您可以假设边缘都是0，因此您可以从位置1,1开始迭代，而不是从0,0开始，因为通过进行dfs，您永远不会超出地图范围。

您应该在maxAreaOfIsland函数中找到“1”瓷砖时重置计数。此外，您可以在dfs之后检查它是否大于您找到的最大值。

class Solution:
    def __init__(self):
        self._count = 0   # You need the count to be visible for both functions, so you can declare it here
        self._maxCount = 0 # Max count doesn't have to be declared here, you can also declare it inside maxAreaOfIsland   

    def maxAreaOfIsland(self, grid):
        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._count = 0   # Here you reset the count
                    self.dfs(grid , x , y)
                    if self._count > self._maxCount:  # Here you check if it's greater than the max
                        self._maxCount = self._count

        return self._maxCount

    def dfs(self,grid, i, j):

        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"
        self._count += 1 # Here you increment the count

        self.dfs(grid , i-1 , j)
        self.dfs(grid , i+1, j)
        self.dfs(grid, i , j-1)
        self.dfs(grid , i , j+1)

- Ghosty Frosty

---

我尝试运行这个程序。但输出是错误的。 - user12852585

你确定你的列表中是字符串而不是整数吗？如果是，请问你是否收到错误信息，或者结果始终是0？我刚在在线解释器上运行了它，似乎结果很好，除了缩进错误和你在dfs中忘记更改索引导致的错误之外。你在dfs中使用的是i和j而不是x和y。@user12852585 - Ghosty Frosty