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
|
from collections import defaultdict, deque
import heapq
# data from archerdata.py, cost map from document
grid = [
[0,0,0,0,0,4,0,0,0,0,3,3,3],
[0,0,0,0,0,4,0,0,0,0,0,3,3],
[0,1,0,0,0,0,4,4,0,0,0,0,0],
[0,1,1,1,0,0,1,4,4,0,0,0,0],
[0,0,0,1,0,0,0,1,1,4,4,4,0],
[0,0,0,0,3,0,0,0,0,0,0,4,4],
[0,0,0,3,3,0,0,1,1,1,0,0,0],
[0,0,3,3,3,0,1,2,1,0,0,0,0],
[0,3,3,4,4,0,0,1,1,0,0,0,0],
[0,4,4,0,0,0,1,0,0,0,0,0,1],
[0,0,4,0,0,0,0,0,0,0,0,1,1],
[0,0,0,0,0,0,3,3,3,1,1,1,0],
[0,0,0,0,0,3,3,1,1,2,2,1,0]
]
cost_map = {0:1, 1:2, 2:3, 3:1, 4:3}
# necessary to convert row and column to tile number
def coords_to_tile(i, j, cols=13):
"""0-based (i,j) → 1-based tile ID"""
return i*cols + j + 1
def tile_to_coords(tile, cols=13):
"""1-based tile ID → 0-based (i,j)"""
t = tile - 1
return divmod(t, cols)
# graph
def build_tile_graph(grid, cost_map):
rows, cols = len(grid), len(grid[0])
g = defaultdict(list)
directions_even = [(-1,-1),(-1,0),(0,-1),(0,1),(1,-1),(1,0)]
directions_odd = [(-1,0),(-1,1),(0,-1),(0,1),(1,0),(1,1)]
for i in range(rows):
for j in range(cols):
u = coords_to_tile(i, j, cols)
dirs = directions_even if i % 2 == 0 else directions_odd
for di, dj in dirs:
ni, nj = i + di, j + dj
if 0 <= ni < rows and 0 <= nj < cols:
v = coords_to_tile(ni, nj, cols)
move_cost = cost_map[ grid[ni][nj] ]
g[u].append((v, move_cost))
return g
# 3) Dijkstra's algorithm
def dijkstra(graph, start, max_cost):
heap = [(0, start)]
dist = {start: 0}
while heap:
cost, u = heapq.heappop(heap)
if cost > max_cost:
continue
for v, c in graph[u]:
nc = cost + c
if nc <= max_cost and (v not in dist or nc < dist[v]):
dist[v] = nc
heapq.heappush(heap, (nc, v))
return dist
if __name__ == "__main__":
graph = build_tile_graph(grid, cost_map)
start_id = 85 # tile "A" in the map
max_moves = 6 # max cost that we can spend moving (per document)
reachable = dijkstra(graph, start_id, max_moves)
result = sorted(reachable.keys())
print(",".join(map(str, result)))
|
