首页 > 代码库 > [leetcode]Surrounded Regions @ Python
[leetcode]Surrounded Regions @ Python
原题地址：https://oj.leetcode.com/problems/surrounded-regions/
题意：
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 XX O O XX X O XX O X X
After running your function, the board should be:
X X X XX X X XX X X XX O X X
解题思路：这道题可以使用BFS和DFS两种方法来解决。DFS会超时。BFS可以AC。从边上开始搜索，如果是‘O‘，那么搜索‘O‘周围的元素，并将‘O‘置换为‘D‘，这样每条边都DFS或者BFS一遍。而内部的‘O‘是不会改变的。这样下来，没有被围住的‘O‘全都被置换成了‘D‘，被围住的‘O‘还是‘O‘，没有改变。然后遍历一遍，将‘O‘置换为‘X‘，将‘D‘置换为‘O‘。
dfs代码，因为递归深度的问题会爆栈：
class Solution: # @param board, a 9x9 2D array # Capture all regions by modifying the input board in-place. # Do not return any value. def solve(self, board): def dfs(x, y): if x<0 or x>m-1 or y<0 or y>n-1 or board[x][y]!=‘O‘:return board[x][y] = ‘D‘ dfs(x-1, y) dfs(x+1, y) dfs(x, y+1) dfs(x, y-1) if len(board) == 0: return m = len(board); n = len(board[0]) for i in range(m): dfs(i, 0); dfs(i, n-1) for j in range(1, n-1): dfs(0, j); dfs(m-1, j) for i in range(m): for j in range(n): if board[i][j] == ‘O‘: board[i][j] == ‘X‘ elif board[i][j] == ‘D‘: board[i][j] == ‘O‘
bfs代码：
class Solution: # @param board, a 2D array # Capture all regions by modifying the input board in-place. # Do not return any value. def solve(self, board): #board最外面四条边上的‘O‘肯定不会被‘X‘包围起来, 从这些‘O‘入手, 使用BFS求出所有相邻的‘O‘, 把这些‘O‘改为另一种符号, 比如‘D‘。然后再扫描一遍board, 把‘O‘换成‘X‘, 把‘D‘换成‘O‘。 def fill(x, y): if x<0 or x>m-1 or y<0 or y>n-1 or board[x][y] != ‘O‘: return queue.append((x,y)) board[x][y]=‘D‘ def bfs(x, y): if board[x][y]==‘O‘: fill(x,y) while queue: curr=queue.pop(0); i=curr[0]; j=curr[1] fill(i+1,j);fill(i-1,j);fill(i,j+1);fill(i,j-1) if len(board)==0: return m=len(board); n=len(board[0]); queue=[] for i in range(n): bfs(0,i); bfs(m-1,i) for j in range(1, m-1): bfs(j,0); bfs(j,n-1) for i in range(m): for j in range(n): if board[i][j] == ‘D‘: board[i][j] = ‘O‘ elif board[i][j] == ‘O‘: board[i][j] = ‘X‘
参考：
本文参考了[1] 但是做了个很小的修改。原文的bfs函数里面多了一个如下操作：queue.append((x,y)) 这个与fill函数的重复了。结果会导致queue每个元素有双备份。
[1] http://www.cnblogs.com/zuoyuan/p/3765434.html
[leetcode]Surrounded Regions @ Python
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。