import collections
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:
return
queue=collections.deque([])
#number of rows
m=len(board)
#number of columns
n=len(board[0])
#put the edge elements into queue
for i in xrange(m):
queue.append((i,0))
queue.append((i,n-1))
for j in xrange(n):
queue.append((0,j))
queue.append((m-1,j))
#examine each edge elements , mark each edge 'O' as 'V' and check its adjacent elements
while queue:
i,j=queue.popleft()
if board[i][j] in ['O','V']:
board[i][j]='V'
for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
if x>=0 and x<m and y>=0 and y<n and board[x][y]=='O':
board[x][y]='V'
queue.append((x,y))
#leave all marked 'V' as 'O', flip all other 'O'
for i in xrange(m):
for j in xrange(n):
if board[i][j]!='V':
board[i][j]='X'
else:
board[i][j]='O'
130. Surrounded Regions
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 这是一道Acceptance不到20%的Medium题。通常这种情况就是有需要细心考虑的边界条件或者递归终止条件。...
- 原题 给一个二维的矩阵，包含 'X' 和 'O', 找到所有被 'X' 围绕的区域，并用 'X' 填充满。 样例给...
- 题目130. Surrounded Regions Given a 2D board containing 'X'...
- [Surrounded Regions](https://leetcode.com/submissions/de...
