|
1
|
|
|
import heapq |
|
2
|
|
|
|
|
3
|
|
|
|
|
4
|
|
View Code Duplication |
def shortestPath(graph, start, end): |
|
|
|
|
|
|
5
|
|
|
queue = [(0, start, [])] |
|
6
|
|
|
seen = set() |
|
7
|
|
|
while True: |
|
8
|
|
|
(cost, v, path) = heapq.heappop(queue) |
|
9
|
|
|
if v not in seen: |
|
10
|
|
|
path = path + [v] |
|
11
|
|
|
seen.add(v) |
|
12
|
|
|
if v == end: |
|
13
|
|
|
return cost, path |
|
14
|
|
|
for (next, c) in graph[v].items(): |
|
15
|
|
|
heapq.heappush(queue, (cost + c, next, path)) |
|
16
|
|
|
return queue |
|
17
|
|
|
|
|
18
|
|
|
|
|
19
|
|
|
def build_network(matrix, TargetNumber): |
|
20
|
|
|
MatrixDict = {} |
|
21
|
|
|
neighbors = [(-1, 0), (0, -1), (0, 1), (1, 0)] |
|
22
|
|
|
matrix = [tuple(['X']) + tuple(i) + tuple(['X']) for i in matrix] |
|
23
|
|
|
matrix = [tuple(['X'] * len(matrix[0]))] + matrix + [tuple(['X'] * len(matrix[0]))] |
|
24
|
|
|
for i in range(len(matrix) - 2): |
|
25
|
|
|
for j in range(len(matrix[0]) - 2): |
|
26
|
|
|
if matrix[i + 1][j + 1] == TargetNumber: |
|
27
|
|
|
if (i, j) not in MatrixDict: |
|
28
|
|
|
MatrixDict[(i, j)] = {} |
|
29
|
|
|
for k in neighbors: |
|
30
|
|
|
if matrix[i + 1 + k[0]][j + 1 + k[1]] == TargetNumber: |
|
31
|
|
|
MatrixDict[(i, j)][(i + k[0], j + k[1])] = 1 |
|
32
|
|
|
return MatrixDict |
|
33
|
|
|
|
|
34
|
|
|
|
|
35
|
|
|
def can_pass(matrix, first, second): |
|
36
|
|
|
TargetNumber = matrix[first[0]][first[1]] |
|
37
|
|
|
try: |
|
38
|
|
|
shortestPath(build_network(matrix, TargetNumber), tuple(first), tuple(second)) |
|
39
|
|
|
return True |
|
40
|
|
|
except IndexError: |
|
41
|
|
|
return False |
|
42
|
|
|
|
|
43
|
|
|
|
|
44
|
|
|
if __name__ == '__main__': |
|
45
|
|
|
assert ( |
|
46
|
|
|
can_pass( |
|
47
|
|
|
( |
|
48
|
|
|
(0, 0, 0, 0, 0, 0), |
|
49
|
|
|
(0, 2, 2, 2, 3, 2), |
|
50
|
|
|
(0, 2, 0, 0, 0, 2), |
|
51
|
|
|
(0, 2, 0, 2, 0, 2), |
|
52
|
|
|
(0, 2, 2, 2, 0, 2), |
|
53
|
|
|
(0, 0, 0, 0, 0, 2), |
|
54
|
|
|
(2, 2, 2, 2, 2, 2), |
|
55
|
|
|
), |
|
56
|
|
|
(3, 2), |
|
57
|
|
|
(0, 5), |
|
58
|
|
|
) |
|
59
|
|
|
is True |
|
60
|
|
|
), 'First example' |
|
61
|
|
|
assert ( |
|
62
|
|
|
can_pass( |
|
63
|
|
|
( |
|
64
|
|
|
(0, 0, 0, 0, 0, 0), |
|
65
|
|
|
(0, 2, 2, 2, 3, 2), |
|
66
|
|
|
(0, 2, 0, 0, 0, 2), |
|
67
|
|
|
(0, 2, 0, 2, 0, 2), |
|
68
|
|
|
(0, 2, 2, 2, 0, 2), |
|
69
|
|
|
(0, 0, 0, 0, 0, 2), |
|
70
|
|
|
(2, 2, 2, 2, 2, 2), |
|
71
|
|
|
), |
|
72
|
|
|
(3, 3), |
|
73
|
|
|
(6, 0), |
|
74
|
|
|
) |
|
75
|
|
|
is False |
|
76
|
|
|
), 'First example' |
|
77
|
|
|
|
KenMercusLai /
checkio
Loading history...