-
Notifications
You must be signed in to change notification settings - Fork 2
/
bfs.py
65 lines (60 loc) · 3.84 KB
/
bfs.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
import queue
dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [1, 1, 0, -1, -1, -1, 0, 1]
width = 5
num = 10
def run(l: list):
s = set(l)
q = queue.Queue()
res = []
while s:
p = s.pop()
q.put(p)
ss = [p]
mp_x = {p[1]: (p[0], p[0])}
mp_y = {p[0]: (p[1], p[1])}
while not q.empty():
p = q.get()
for (x, y) in zip(dx, dy):
nx, ny = x + p[0], y + p[1]
if (nx, ny) in s:
q.put((nx, ny))
ss.append((nx, ny))
mp_x[ny] = (min(mp_x[ny][0] if ny in mp_x else nx, nx), max(mp_x[ny][1] if ny in mp_x else nx, nx))
mp_y[nx] = (min(mp_y[nx][0] if nx in mp_y else ny, ny), max(mp_y[nx][1] if nx in mp_y else ny, ny))
s.remove((nx, ny))
max_wx = 0
max_wy = 0
for value in mp_x.values():
max_wx = max(max_wx, value[1] - value[0] + 1)
for value in mp_y.values():
max_wy = max(max_wy, value[1] - value[0] + 1)
if len(ss) > num and (max_wx <= width or max_wy <= width):
res.append(ss)
return res
if __name__ == '__main__':
ll = [(462, 1510), (462, 1511), (463, 1509), (463, 1510), (463, 1511), (464, 1508), (464, 1509), (464, 1510),
(465, 1506), (465, 1507), (465, 1508), (465, 1509), (466, 1505), (466, 1506), (466, 1507), (467, 1504),
(467, 1505), (467, 1506), (468, 1503), (468, 1504), (468, 1505), (469, 1502), (469, 1503), (469, 1504),
(470, 1500), (470, 1501), (470, 1502), (470, 1503), (471, 1499), (471, 1500), (471, 1501), (472, 1498),
(472, 1499), (472, 1500), (473, 1498), (473, 1499), (474, 1498), (482, 1340), (483, 1340), (483, 1341),
(483, 1342), (483, 1343), (484, 1340), (484, 1341), (484, 1342), (484, 1343), (484, 1344), (484, 1345),
(485, 1343), (485, 1344), (485, 1345), (485, 1346), (485, 1347), (485, 1348), (486, 1346), (486, 1347),
(486, 1348), (486, 1349), (486, 1350), (486, 1351), (487, 1349), (487, 1350), (487, 1351), (487, 1352),
(487, 1353), (487, 1354), (488, 1352), (488, 1353), (488, 1354), (488, 1355), (488, 1356), (488, 1357),
(489, 1355), (489, 1356), (489, 1357), (489, 1358), (489, 1359), (489, 1360), (490, 1357), (490, 1358),
(490, 1359), (490, 1360), (490, 1361), (490, 1362), (490, 1363), (491, 1360), (491, 1361), (491, 1362),
(491, 1363), (491, 1364), (491, 1365), (492, 1363), (492, 1364), (492, 1365), (492, 1366), (492, 1367),
(492, 1368), (493, 1366), (493, 1367), (493, 1368), (493, 1369), (493, 1370), (493, 1371), (494, 1369),
(494, 1370), (494, 1371), (494, 1372), (494, 1373), (494, 1374), (495, 1372), (495, 1373), (495, 1374),
(495, 1375), (495, 1376), (495, 1377), (496, 1374), (496, 1375), (496, 1376), (496, 1377), (496, 1378),
(496, 1379), (496, 1380), (497, 1377), (497, 1378), (497, 1379), (497, 1380), (497, 1381), (497, 1382),
(498, 1380), (498, 1381), (498, 1382), (498, 1383), (503, 1454), (538, 1458), (538, 1459), (539, 1458),
(539, 1459), (540, 1459), (540, 1460), (541, 1459), (541, 1460), (541, 1461), (542, 1460), (542, 1461),
(542, 1462), (543, 1461), (543, 1462), (543, 1463), (544, 1462), (544, 1463), (545, 1463), (545, 1464),
(546, 1463), (546, 1464), (546, 1465), (547, 1464), (547, 1465), (547, 1466), (548, 1465), (548, 1466),
(548, 1467), (549, 1466), (549, 1467), (549, 1468), (550, 1467), (550, 1468), (551, 1468), (551, 1469),
(552, 1468), (552, 1469), (552, 1470), (553, 1469), (553, 1470), (553, 1471), (554, 1470), (554, 1471),
(554, 1472), (555, 1471), (555, 1472), (556, 1472), (556, 1473), (557, 1472), (557, 1473), (557, 1474),
(558, 1473), (558, 1474), (558, 1475), (559, 1474), (559, 1475), (559, 1476)]
print(len(run(ll)))