那种导航网站百度推广登录首页
本文由我司收集整编，推荐下载，如有疑问，请与我司联系
[LeetCode]
题解(
python
)：
130
2016/03/22 0
题意分析：
给定给一个二维的板，这个板只包括‘
X
’和‘
O
’
。将被‘
X
’包围的‘
O
’变
成‘
X
’
。比如：
X X X XX O O XX X O XX O X X
得到：
X X X XX X X XX X X XX O X X
题目思路：
从板的周围出发，从周围的‘
O
’出发深度搜索，能搜到的‘
O
’用
visit
记录
他有没有访问过。最后将所有没有
visit
过的
’O’
变成‘
X
’
.
代码(
python
)：
1
class
Solution(object):
2
def
solve(self,
board):
3
“““
4
:type
board:
List[List[str]] 5 :rtype: void Do not return anything, modify board in-place instead. 6 “““ 7
m = len(board) 8 if m == 0: 9 return10 n = len(board[0])11 visit = [[False for i in range(n)]
for j in range(m)]12 def dfs(i,j):13 q = []14 q.append([i,j])15 while len(q) != 0:16 tmp =
q[0]17 #print(tmp,visit[3][1],board[3][1])18 q.pop(0)19 #down,up,left,right20 if tmp[0] - 1
0
and
board[tmp[0]
-
1][tmp[1]]
==
‘O’
and
visit[tmp[0]-1][tmp[1]]
==
False:21
visit[tmp[0]
-1][tmp[1]]
=
True22
q.append([tmp[0]
-
1,tmp[1]])23
if
tmp[0]
+
1
m
and
board[tmp[0]
+
1][tmp[1]]
==
‘O’
and
visit[tmp[0]+1][tmp[1]]
==
False:24
visit[tmp[0]
+1][tmp[1]]
=
True25
q.append([tmp[0]
+
1,tmp[1]])26
if
tmp[1]
-
1
0
and
board[tmp[0]][tmp[1]
-
1]
==
‘O’
and
visit[tmp[0]][tmp[1]-1]
==
False:27
visit[tmp[0]][tmp[1]
-
1]
=
True28
q.append([tmp[0],tmp[1]
-
1])29
if
tmp[1]
+
1
n
and
board[tmp[0]][tmp[1]
+
1]
==
‘O’
and
visit[tmp[0]][tmp[1]+1]
==
False:30
visit[tmp[0]][tmp[1]+1]
=
True31
q.append([tmp[0],tmp[1]+1])32
for
i
in
range(n):33
if
visit[0][i]
==
False
and
board[0][i]
==
‘O’:34
visit[0][i]
=
True35
dfs(0,i)36
if
visit[m
-
1][i] == False and board[m-1][i] == ‘O’:37 visit[m-1][i] = True38 dfs(m - 1,i)39 for j in
range(m):40 if visit[j][0] == False and board[j][0] == ‘O’:41 visit[j][0] = True42 dfs(j,0)43