实施 DFS 以查找矩阵中的孤岛时出现问题
Problem implementing DFS to find islands in a matrix
我正在尝试解决一个名为 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。我不确定为什么以及这里出了什么问题
请注意,将列表相乘会创建对相关列表的多个引用,而不是多个副本。所以 [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))]
),但最好养成前者的习惯。
我正在尝试解决一个名为 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。我不确定为什么以及这里出了什么问题
请注意,将列表相乘会创建对相关列表的多个引用,而不是多个副本。所以 [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))]
),但最好养成前者的习惯。