Проблема реализации DFS для поиска островков в матрице

Question

Я пытаюсь решить проблему кода 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)

По какой-то причине в моей посещаемой матрице для каждого столбца установлено значение true после каждого вызова dfs. Я не уверен, почему и что здесь не так

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))]), но, вероятно, лучше привыкнуть к первым.