|
2 | 2 | coords = {x+1j*y: c for y, r in enumerate(open(0)) for x, c in enumerate(r.strip())} |
3 | 3 |
|
4 | 4 | G = nx.DiGraph() |
5 | | - |
6 | 5 | for c in coords: |
7 | | - if coords[c] == '#': continue |
8 | 6 | for d in [1, 1j, -1, -1j]: |
9 | | - G.add_edge((c, d), c, weight=0) |
10 | | - G.add_edge(c, (c, d), weight=1000) |
11 | | - if coords[c+d] != '#': |
| 7 | + G.add_edge((c, d), (c, 0), weight=0) |
| 8 | + G.add_edge((c, 0), (c, d), weight=1000) |
| 9 | + if coords[c] != '#' != coords[c+d]: |
12 | 10 | G.add_edge((c, d), (c+d, d), weight=1) |
13 | 11 |
|
14 | | -S = [c for c in coords if coords[c] == 'S'][0] |
15 | | -E = [c for c in coords if coords[c] == 'E'][0] |
| 12 | +E, S = [c for c in coords if coords[c] in 'SE'] |
16 | 13 |
|
17 | | -all_paths = list(nx.all_shortest_paths(G, (S, 1), E, "weight")) |
18 | | -path = all_paths[0] |
19 | | -print(sum(G.edges[edge]["weight"] for edge in zip(path, path[1:]))) |
| 14 | +paths = list(nx.all_shortest_paths(G, (S, 1), (E, 0), "weight")) |
20 | 15 |
|
21 | | -flat = sum(all_paths, []) |
22 | | -nodes = {(p[0] if isinstance(p, tuple) else p) for p in flat} |
23 | | -print(len(nodes)) |
| 16 | +print(sum(G.edges[e]["weight"] for e in zip(paths[0], paths[0][1:]))) |
| 17 | +print(len({p[0] for p in sum(paths, [])})) |
0 commit comments