实施 DFS 以查找矩阵中的孤岛时出现问题

Question

我正在尝试解决一个名为 Number of Islands

的 leetcode 问题

给定“1”（陆地）和“0”（水）的二维网格地图，计算岛屿的数量。岛屿四面环水，由相邻陆地水平或垂直连接而成。您可以假设网格的所有四个边缘都被水包围。

class Solution(object):
    def numIslands(self, grid):
        if len(grid) == 0 or len(grid[0]) == 0:
            return 0

        visited = [[False]*len(grid[0])]*len(grid)
        count = 0

        grid = [[int(k) for k in item] for item in grid]

        for i in range(0, len(grid)):
            for j in range(0, len(grid[0])):
                if visited[i][j] == False and grid[i][j] == 1:
                    print('new island---->', i, j)
                    count = count+1
                    self.dfs(grid, visited, i, j)

    def dfs(self, grid, visited, i, j):
        if i >= len(grid) or j >= len(grid[0]):
            return 
        elif grid[i][j] == 0:
            return 
        else:
            visited[i][j] = True
            self.dfs(grid, visited, i+1, j)
            self.dfs(grid, visited, i, j+1)

出于某种原因，我访问的矩阵在每次 dfs 调用后将整个列设置为 true。我不确定为什么以及这里出了什么问题

Answer 1

请注意，将列表相乘会创建对相关列表的多个引用，而不是多个副本。所以 [x] * 2 产生 [x, x]，而不是 [copy.copy(x), copy.copy(x)]，如果 x 是可变的，这是一个重要的区别。因此，在初始化 visited 时，您需要使用列表理解而不是列表乘法：[[False for _ in range(len(grid[0]))] for _ in range(len(grid))]。这将为每个元素创建一个新列表。

因为 False 是不可变的，您可以对内部列表使用乘法 ([[False] * len(grid[0]) for _ in range(len(grid))])，但最好养成前者的习惯。

实施 DFS 以查找矩阵中的孤岛时出现问题

Problem implementing DFS to find islands in a matrix

python

algorithm

recursion

depth-first-search

breadth-first-search