# 130 surrounded regions

### 130. Surrounded Regions

https://leetcode.com/problems/surrounded-regions

Medium

loop，然后碰到O做DFS/BFS找出O所在区域:

• 貌似只要O没有碰壁，O就总是被X包围着？
• 所以找出O的范围，然后看它是否碰壁，没有碰壁则mark不需要修改

class Solution(object):
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""

def shouldOChange(i, j):
"""
return x,y area and whether they shouldChange
"""
shouldChange = True
Oarea = []
s = []
s.append((i,j))
while s:
(x,y) = s.pop()
if x == 0 or x == row - 1 or y == 0 or y == col -1 :
shouldChange = False
visited[x][y] = 1
Oarea.append((x,y))
if legal(x-1,y):
s.append((x-1,y))
if legal(x+1,y):
s.append((x+1,y))
if legal(x,y-1):
s.append((x,y-1))
if legal(x,y-1):
s.append((x,y+1))
return Oarea,shouldChange

def legal(x,y):
return x>=0 and x < row and y>=0 and y < col and board[x][y] == 'O' and visited[x][y] == 0

row = len(board)
col = len(board[0]) if row else 0

visited = [[0 for i in range(col)] for j in range(row)]

for i in range(row):
for j in range(col):
if board[i][j] == 'O' and visited[i][j] == 0:
Oarea, shouldChange = shouldOChange(i,j)
print Oarea,shouldChange
if shouldChange:
for (x,y) in Oarea:
board[x][y] = u'X'

print board


AC代码

class Solution(object):
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
def legal(x,y):
return x>=0 and x < row and y>=0 and y < col and board[x][y] == 'O' and visited[x][y] == 0

row = len(board)
col = len(board[0]) if row else 0

visited = [[0 for i in range(col)] for j in range(row)]

notChangeOArea = []
queue = collections.deque()

for j in range(col):
if board[0][j] == 'O': queue.append((0,j))
if board[row-1][j] == 'O': queue.append((row-1,j))
for i in range(row):
if board[i][0] == 'O': queue.append((i,0))
if board[i][col-1] == 'O': queue.append((i,col-1))

while queue:
(x,y) = queue.popleft()
board[x][y] = '$' visited[x][y] = 1 if legal(x-1,y): queue.append((x-1,y)) if legal(x+1,y): queue.append((x+1,y)) if legal(x,y-1): queue.append((x,y-1)) if legal(x,y+1): queue.append((x,y+1)) for i in range(row): for j in range(col): if board[i][j] == '$' : board[i][j] = 'O'
elif board[i][j] == 'O' : board[i][j] = 'X'


apachecn/AiLearning