Total Accepted: 43584 Total Submissions: 284350 Difficulty: Medium
Given a 2D board containing 'X'
and 'O'
, capture all regions surrounded by 'X'
.
A region is captured by flipping all 'O'
s into 'X'
s in that surrounded region.
For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X 反向思考,可以从四边开始找O,这些外面的O都找出来以后剩下的就是被包围的O了,非递归的BFS和DFS都可以AC(递归的很可能爆栈),找出外面的O并替换为A,剩下的所有的O就是要找的,flip为X即可,再把A替换为O
AC之后的结果来看,DFS所需时间是BFS两倍。 BFS实现:
class Solution(object):
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
if board==[]:
return
width = len(board[0])
height = len(board)
edgeNods=[]
for column in range(width): #todo: all edgeNode
edgeNode = (0, column)
if board[0][column]=='O':
edgeNods.append(edgeNode)
for line in range(height): #todo: all edgeNode
edgeNode = (line, 0)
if board[line][0]=='O':
edgeNods.append(edgeNode)
for column in range(width): #todo: all edgeNode
edgeNode = (height-1, column)
if board[height-1][column]=='O':
edgeNods.append(edgeNode)
for line in range(height): #todo: all edgeNode
edgeNode = (line, width-1)
if board[line][width-1]=='O':
edgeNods.append(edgeNode) stack = edgeNods
while stack:
nod = stack.pop(0)
if board[nod[0]][nod[1]] == 'X' or board[nod[0]][nod[1]] == 'A' :
continue
else:
board[nod[0]][nod[1]] = 'A' neighbours=[]
neighbours.append((nod[0]-1, nod[1]))
neighbours.append((nod[0]+1, nod[1]))
neighbours.append((nod[0], nod[1]-1))
neighbours.append((nod[0], nod[1]+1))
for neiber in neighbours:
if neiber[0]<0 or neiber[0] >= height \
or neiber[1] <0 or neiber[1] >= width:
continue
if board[neiber[0]][neiber[1]] == 'X' or board[neiber[0]][neiber[1]] == 'A' :
continue
if (neiber in stack):
continue
stack.append(neiber) for column in range(width):
for line in range(height):
if board[line][column] == 'O':
board[line][column]= "X"
for column in range(width):
for line in range(height):
if board[line][column] == 'A':
board[line][column]='O'