题目来源:
https://leetcode.com/problems/surrounded-regions/
题意分析:
给定给一个二维的板,这个板只包括‘X’和‘O’。将被‘X’包围的‘O’变成‘X’。比如:
X X X X
X O O X
X X O X
X O X X
得到:
X X X X
X X X X
X X X X
X O X X
题目思路:
从板的周围出发,从周围的‘O’出发深度搜索,能搜到的‘O’用visit记录他有没有访问过。最后将所有没有visit过的'O'变成‘X’.
代码(python):
class Solution(object):
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
m = len(board)
if m == 0:
return
n = len(board[0])
visit = [[False for i in range(n)] for j in range(m)]
def dfs(i,j):
q = []
q.append([i,j])
while len(q) != 0:
tmp = q[0]
#print(tmp,visit[3][1],board[3][1])
q.pop(0)
#down,up,left,right
if tmp[0] - 1 > 0 and board[tmp[0] - 1][tmp[1]] == 'O' and visit[tmp[0]-1][tmp[1]] == False:
visit[tmp[0] -1][tmp[1]] = True
q.append([tmp[0] - 1,tmp[1]])
if tmp[0] + 1 < m and board[tmp[0] + 1][tmp[1]] == 'O' and visit[tmp[0]+1][tmp[1]] == False:
visit[tmp[0] +1][tmp[1]] = True
q.append([tmp[0] + 1,tmp[1]])
if tmp[1] - 1 > 0 and board[tmp[0]][tmp[1] - 1] == 'O' and visit[tmp[0]][tmp[1]-1] == False:
visit[tmp[0]][tmp[1] - 1] = True
q.append([tmp[0],tmp[1] - 1])
if tmp[1] + 1 < n and board[tmp[0]][tmp[1] + 1] == 'O' and visit[tmp[0]][tmp[1]+1] == False:
visit[tmp[0]][tmp[1]+1] = True
q.append([tmp[0],tmp[1]+1])
for i in range(n):
if visit[0][i] == False and board[0][i] == 'O':
visit[0][i] = True
dfs(0,i)
if visit[m - 1][i] == False and board[m-1][i] == 'O':
visit[m-1][i] = True
dfs(m - 1,i)
for j in range(m):
if visit[j][0] == False and board[j][0] == 'O':
visit[j][0] = True
dfs(j,0)
if visit[j][n - 1] == False and board[j][n - 1] == 'O':
visit[j][n - 1] = True
dfs(j,n - 1)
for i in range(m):
for j in range(n):
if board[i][j] == 'O' and not visit[i][j]:
board[i][j] = 'X'