软件开发公司网站模板,上海都市建筑设计有限公司,教育培训加盟,网络服务器建设本文由我司收集整编#xff0c;推荐下载#xff0c;如有疑问#xff0c;请与我司联系 [LeetCode] 题解( python )#xff1a; 130 2016/03/22 0 题意分析#xff1a; 给定给一个二维的板#xff0c;这个板只包括‘ X ’和‘ O ’ 。将被‘ X ’包围的‘ O ’变 成‘ X ’… 本文由我司收集整编推荐下载如有疑问请与我司联系 [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
