Lintcode 477. Surrounded Regions (Medium) (Python)
4112 ワード
Surrounded Regions
Description:
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.
Example X X X X X O O X X X O X X O X X After capture all regions surrounded by ‘X’, the board should be:
X X X X X X X X X X X X X O X X
Code:
Description:
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.
Example X X X X X O O X X X O X X O X X After capture all regions surrounded by ‘X’, the board should be:
X X X X X X X X X X X X X O X X
Code:
class Solution:
"""
@param: board: board a 2D board containing 'X' and 'O'
@return: nothing
"""
def surroundedRegions(self, board):
# write your code here
if not board:
return board
def switch(x, y):
board[x][y] = 'A'
if x!=0 and board[x-1][y]=='O':
switch(x-1, y)
if x!=lx-1 and board[x+1][y]=='O':
switch(x+1, y)
if y!=0 and board[x][y-1]=='O':
switch(x, y-1)
if y!=ly-1 and board[x][y+1]=='O':
switch(x, y+1)
lx = len(board)
ly = len(board[0])
for i in range(ly):
if board[0][i]=='O':
switch(0, i)
if board[lx-1][i]=='O':
switch(lx-1, i)
for i in range(lx):
if board[i][0]=='O':
switch(i, 0)
if board[i][ly-1]=='O':
switch(i, ly-1)
for i in range(lx):
for j in range(ly):
if board[i][j]=='O':
board[i][j]='X'
if board[i][j]=='A':
board[i][j]='O'