-
Notifications
You must be signed in to change notification settings - Fork 0
/
130. 被围绕的区域.py
102 lines (90 loc) · 4.66 KB
/
130. 被围绕的区域.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#!/usr/bin/env python
# _*_coding:utf-8 _*_
"""
@Time :2020/8/11 11:22 下午
@Author :[email protected]
@File :130. 被围绕的区域.py
@Description :
"""
class Solution(object):
def __init__(self):
self.dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: None Do not return anything, modify board in-place instead.
"""
if len(board) == 0 or len(board[0]) == 0:
return
# 1.先找出边上的O
for i in range(4):
if i == 0:
# 第一行
for j in range(len(board[0])):
if board[0][j] == 'O':
board[0][j] = 'Y'
for dir in self.dirs:
dir_x = dir[0]
dir_y = dir[1]
self.track(board, dir_x, j + dir_y)
pass
pass
if i == 1:
# 第一列
for j in range(len(board)):
if board[j][0] == 'O':
board[j][0] = 'Y'
for dir in self.dirs:
dir_x = dir[0]
dir_y = dir[1]
self.track(board, j + dir_x, dir_y)
pass
pass
if i == 2:
# 最后一行
for j in range(len(board[0])):
if board[-1][j] == 'O':
board[-1][j] = 'Y'
for dir in self.dirs:
dir_x = dir[0]
dir_y = dir[1]
self.track(board, len(board) - 1 + dir_x, j + dir_y)
pass
pass
if i == 3:
# 最后一列
for j in range(len(board)):
if board[j][-1] == 'O':
board[j][-1] = 'Y'
for dir in self.dirs:
dir_x = dir[0]
dir_y = dir[1]
self.track(board, j + dir_x, len(board[0]) - 1 + dir_y)
pass
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == 'O':
board[i][j] = 'X'
if board[i][j] == 'Y':
board[i][j] = 'O'
def track(self, board, i, j):
if i >= len(board) or j >= len(board[0]) or i < 0 or j < 0:
return
if board[i][j] == 'O':
board[i][j] = 'Y'
for dir in self.dirs:
dir_x = dir[0]
dir_y = dir[1]
self.track(board, i + dir_x, j + dir_y)
else:
return
pass
if __name__ == '__main__':
board = [
["X","O","X","X"],
["X","O","X","X"],
["X","X","O","X"],
["X","O","X","X"]]
board =[["O","X","X","X","X","O","O","X","O","X","X","X","X","X","X","O","O","X","X","O"],["O","O","O","O","O","O","X","O","X","O","X","O","O","X","X","O","O","O","X","O"],["O","X","O","X","O","X","O","X","O","O","X","X","X","O","O","O","O","O","O","X"],["X","O","O","X","X","X","X","X","O","X","O","O","O","O","X","O","X","O","X","O"],["O","X","O","O","O","O","X","O","O","O","O","X","O","O","X","O","X","X","X","O"],["O","O","O","O","O","O","O","X","O","X","X","O","O","X","X","O","O","X","O","X"],["O","O","X","X","X","X","O","X","X","X","X","O","O","O","X","O","X","O","X","X"],["X","X","X","X","O","O","X","O","X","O","O","O","O","O","O","X","X","X","O","X"],["X","O","O","O","X","X","O","O","X","O","X","X","O","O","O","X","O","O","O","O"],["X","O","O","X","O","X","O","X","O","O","X","X","X","O","O","O","O","O","X","O"],["O","O","O","X","O","O","X","O","O","O","O","O","O","X","O","X","O","O","X","X"],["O","X","O","O","X","X","X","O","X","X","X","O","O","O","X","O","X","O","O","O"],["X","X","X","O","X","X","O","X","O","X","O","X","X","O","O","O","X","O","O","O"],["O","X","X","O","X","O","O","X","X","O","X","X","O","X","X","O","X","X","O","O"],["O","X","X","O","O","X","O","O","O","X","O","X","O","O","O","O","O","O","X","X"],["O","O","X","O","O","O","X","X","O","X","X","X","X","O","X","O","X","O","X","O"],["X","O","O","O","X","O","X","O","X","O","O","O","O","X","X","O","O","O","O","O"],["X","O","O","X","X","O","O","X","X","O","O","O","X","O","O","O","X","X","X","O"],["O","X","O","X","X","O","O","O","X","X","O","O","X","X","X","O","O","X","X","O"],["O","O","X","O","X","O","O","O","O","O","O","O","O","X","O","X","O","O","X","O"]]
Solution().solve(board)
print board