描述
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
构成的路径通往边界,它就是安全的(不会被X
掉)。我们从边缘四周的O
开始做深度或广度优先遍历,把安全的O
都标记起来。
代码
BFS(会超时)
1 |
from collections import deque |
优化后的BFS
1 |
from collections import deque |
近期评论