forked from HuberTRoy/leetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
SurroundedRegions.py
180 lines (145 loc) · 5.92 KB
/
SurroundedRegions.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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
"""
Given a 2D board containing 'X' and 'O' (the letter 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 running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
Explanation:
Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'.
Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'.
Two cells are connected if they are adjacent cells connected horizontally or vertically.
给一个二维数组里面是 'X' 和 'O'，所有并未连着任何边界的 'O' 都变成 'X' 即可。
X X X X
X X O O
X O X X
X X X X
变形后为
X X X X
X X O O
X X X X
X X X X
思路：
1. 一开始用递归，迭代每一个点，把里面所有的和带边界的 O 及其相邻的找出来，把不相邻的 和 相邻的 分别放到两个坐标列表里，然后进行 'O' 'X' 的分配..
这个思路和写法都没问题... 无奈的是测试数据过大会导致超过最大递归深度，而且比较慢。
放弃。
2. 这个思路沿用上一个的思路，只不过这次所做的是只迭代四周的即可。 因为不与四周的 'O' 相邻的是不需要在一开始就变得。
所以只迭代找出四周的 'O' 并用递归把它的邻居们都变成另一个字符，或者存坐标也可以。
之后迭代原地图，然后把是标识的变回 'O'，原来是 'O' 的变成 'X' 即可。
效率 O(row*column)
测试链接：
https://leetcode.com/problems/surrounded-regions/description/
beat 40%~60%.
时间上可以通过一些细节做优化，能提升数毫秒，不过就此题来说没有必要，前面的基本都是这个思路。
"""
class Solution(object):
def makeAround(self, x, y):
# if x - 1 >= 0 and y - 1 >= 0 and x + 1 < x_maxes and y + 1 < y_maxes:
# return True
# right left down up
return [(y, x-1),
(y, x+1),
(y-1, x),
(y+1, x)]
# return False
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
# return board
if not board:
x_length = 0
else:
x_length = len(board[0])
y_length = len(board)
def translate_o_to_e(x, y):
# pass
# coordinate = self.makeAround(x, y)
# if coordinate:
for i in self.makeAround(x, y):
if i[0] >= 0 and i[1] >= 0 and i[0] < y_length and i[1] < x_length:
if board[i[0]][i[1]] == "O":
board[i[0]][i[1]] = "E"
translate_o_to_e(i[1], i[0])
# up down
e_coordinate = []
for i in range(x_length):
if board[0][i] == 'O':
board[0][i] = 'E'
translate_o_to_e(i, 0)
if board[y_length-1][i] == "O":
board[y_length-1][i] = 'E'
translate_o_to_e(i, y_length-1)
# left right
for i in range(y_length):
if board[i][0] == 'O':
board[i][0] = 'E'
translate_o_to_e(0, i)
if board[i][x_length-1] == 'O':
board[i][x_length-1] = 'E'
translate_o_to_e(x_length-1, i)
for y in range(y_length):
for x in range(x_length):
if board[y][x] == 'E':
board[y][x] = 'O'
elif board[y][x] == 'O':
board[y][x] = 'X'
# e_coordinate = []
# for y in range(y_length):
# for x in range(x_length):
# if board[y][x] == 'O':
# coordinate = self.makeAround(x, y, x_length, y_length)
# if not coordinate:
# board[y][x] = 'E'
# e_coordinate.append((y, x))
# else:
# for i in coordinate:
# if board[i[0]][i[1]] == 'E':
# board[y][x] = 'E'
# e_coordinate.append((y, x))
# break
# else:
# board[y][x] = 'X'
# for i in e_coordinate:
# board[i[0]][i[1]] = 'O'
# def found_o(y, x):
# result = []
# coordinate = self.makeAround(x, y, x_length, y_length)
# if not coordinate:
# return False, result
# for i in coordinate:
# if board[i[0]][i[1]] == 'O':
# board[i[0]][i[1]] = 'E'
# x = found_o(i[0], i[1])
# result.append(i)
# result.extend(x[1])
# if not x[0]:
# return False, result
# return True, result
# o_coordinate = []
# x_coordinate = []
# for y in range(y_length):
# for x in range(x_length):
# if board[y][x] == 'O':
# x = found_o(y, x)
# if x[0]:
# x_coordinate.extend(x[1])
# else:
# o_coordinate.extend(x[1])
# # print(o_coordinate)
# for i in o_coordinate:
# board[i[0]][i[1]] = 'O'
# # print(x_coordinate)
# for i in x_coordinate:
# # print(i)
# board[i[0]][i[1]] = 'X'
# coordinate = self.makeAround(x, y, x_length, y_length)
# if coordinate:
# board[y][x] = 'X'