LeetCode130求教
来源：8-7 floodfill算法，一类经典问题 Number of Islands-
qq_山上山_0
2022-04-07
波波老司，23/58的用例没通过，但是很不理解，
输入 board = [[“X”,“O”,“X”], [“X”,“O”,“X”],[“X”,“O”,“X”]]
为什么结果是 [[‘X’, ‘O’, ‘X’], [‘X’, ‘X’, ‘X’], [‘X’, ‘O’, ‘X’]] （python3）
class Solution:
m, n = 0, 0
d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
used = []
def isSide(self, x, y): #靠边的
return x == 0 or x == self.m - 1 or y == 0 or y == self.n - 1
def isArea(self, x, y): #棋盘内的
return 0 <= x and x < self.m and 0 <= y and y < self.n
def isIn(self, x, y): #距离边界为1的
return 1 <= x and x < self.m - 1 and 1 <= y and y < self.n - 1
def donotChangeX(self, board, startx, starty): #把与靠边的'O'都标记为已使用
self.used[startx][starty] = True
for i in range(4):
newx = startx + self.d[i][0]
newy = starty + self.d[i][1]
if self.isArea(newx, newy) == True and self.used[newx][newy] == False and \
board[newx][newy] == 'O':
self.donotChangeX(board, newx, newy)
return
def changeX(self, board, startx, starty): #合理范围内的 dfs
board[startx][starty] = 'X'
self.used[startx][starty] = True
for i in range(4):
newx = startx + self.d[i][0]
newy = starty + self.d[i][1]
if self.used[newx][newy] == False and board[newx][newy] == 'O' and \
self.isIn(newx, newy) == True:
self.changeX(board, newx, newy)
# print(board)
return
def solve(self, board) -> None:
"""
Do not return anything, modify board in-place instead.
"""
self.m = len(board)
if self.m > 0:
self.n = len(board[0])
self.used = [[False] * self.n for i in range(self.m)]
for i in range(self.m):
for j in range(self.n):
if self.isSide(i, j) == True and board[i][j] == 'O' and self.used[i][j] == False:
self.donotChangeX(board, i, j)
continue
if self.used[i][j] == False and self.isIn(i, j) == True and board[i][j] == 'O':
self.changeX(board, i, j)
print(board)
写回答
1回答
-
liuyubobobo
2022-04-07
最大的逻辑问题是，你在一边标记和边缘相连接的区域，一边去把没有和边缘相连接的区域标记成 X。但是，当你访问一个没有和边缘相连接的中心区域的时候，和它相连接的边缘可能还没有标记（在它的右边或者下边或者左下边，根据你的逻辑还没有遍历到）。
所以，你需要先标记所有的边缘，再遍历中心区域。
代码中的一个“粗心”的地方是，donotChangeX 中的 return 缩进不正确。
==========
以下代码是我根据你的代码1做的修改，可以 AC。
class Solution: m, n = 0, 0 d = [[0, 1], [1, 0], [0, -1], [-1, 0]] used = [] def isSide(self, x, y): #靠边的 return x == 0 or x == self.m - 1 or y == 0 or y == self.n - 1 def isArea(self, x, y): #棋盘内的 return 0 <= x and x < self.m and 0 <= y and y < self.n def isIn(self, x, y): #距离边界为1的 return 1 <= x and x < self.m - 1 and 1 <= y and y < self.n - 1 def donotChangeX(self, board, startx, starty): #把与靠边的'O'都标记为已使用 self.used[startx][starty] = True for i in range(4): newx = startx + self.d[i][0] newy = starty + self.d[i][1] if self.isArea(newx, newy) == True and self.used[newx][newy] == False and \ board[newx][newy] == 'O': self.donotChangeX(board, newx, newy) return def changeX(self, board, startx, starty): #合理范围内的 dfs board[startx][starty] = 'X' self.used[startx][starty] = True for i in range(4): newx = startx + self.d[i][0] newy = starty + self.d[i][1] if self.used[newx][newy] == False and board[newx][newy] == 'O' and \ self.isIn(newx, newy) == True: self.changeX(board, newx, newy) # print(board) return def solve(self, board) -> None: """ Do not return anything, modify board in-place instead. """ self.m = len(board) if self.m > 0: self.n = len(board[0]) self.used = [[False] * self.n for i in range(self.m)] # 先标记边缘 for i in range(self.m): if board[i][0] == 'O' and self.used[i][0] == False: self.donotChangeX(board, i, 0) if board[i][self.n - 1] == 'O' and self.used[i][self.n - 1] == False: self.donotChangeX(board, i, self.n - 1) for j in range(self.n): if board[0][j] == 'O' and self.used[0][j] == False: self.donotChangeX(board, 0, j) if board[self.m - 1][j] == 'O' and self.used[self.m - 1][j] == False: self.donotChangeX(board, self.m - 1, j) # 再遍历中心 for i in range(1, self.m - 1): for j in range(1, self.n - 1): if self.used[i][j] == False and board[i][j] == 'O': self.changeX(board, i, j) print(board)
继续加油！：）
212022-04-07
相似问题