【Leetcode】【python】Surrounded Regions 被围绕的区域

题目大意

有一个二维的面板,上面由”X”或者”O”填充。现在要求将被”X”包围的”O”都改成”X”。

解题思路

参考:

https://shenjie1993.gitbooks.io/leetcode-python/130%20Surrounded%20Regions.html

直接去找被X包围的O比较麻烦,不如转换一下思路,找出哪些O是没有被X包围的。

首先在面板四周的O肯定是没有被X包围的,与它们相连的O也是没有被包围的,其它的O都是被X包围的。

问题简化为将与四周的O相连的O都找出来,这些点不用变,其它点都变为X。

首先将四周的O压入栈内,依次访问栈内元素,并将它们标记,接着去判断它们四周的元素是否也是O,如果是且没有被标记过,则将其压入栈中。

当遍历完栈中的元素后,将有标记的元素变为O,其余都是X。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution(object):
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
if not board or not board[0]:
return
n = len(board)
m = len(board[0])
queue = []
# 保存所有位于边缘的O
for i in range(n):
for j in range(m):
if ((i in (0, n - 1)) or (j in (0, m - 1))) and board[i][j] == 'O': # i in (0, n - 1) 最上面和最下面两排
queue.append((i, j))
print (i,j)
# 保存所有与边缘O相连的O
while queue:
r, c = queue.pop(0) # i, j = r, c
if 0 <= r < n and 0 <= c < m and board[r][c] == 'O':
board[r][c] = 'M' # 变为M的则是不需要变成X的
if r - 1 >= 0 and board[r - 1][c] == 'O':
queue.append((r - 1, c))
if r + 1 < n and board[r + 1][c] == 'O':
queue.append((r + 1, c))
if c - 1 >= 0 and board[r][c - 1] == 'O':
queue.append((r, c - 1))
if c + 1 < m and board[r][c + 1] == 'O':
queue.append((r, c + 1))
# 重新更新棋盘
for i in range(n):
for j in range(m):
if board[i][j] == 'M':
board[i][j] = 'O'
else:
board[i][j] = 'X'

总结

还可以用union-find法
https://blog.csdn.net/guoziqing506/article/details/78752557