12.jl (3603B)
1 function popmin!(avail, dist) 2 local min = () 3 local mindist = length(dist) 4 for v in avail 5 if (dist[v[1], v[2]] < mindist) 6 mindist = dist[v[1], v[2]] 7 min = v 8 end 9 end 10 delete!(avail, min) 11 return min 12 end 13 14 # Slow and brute force implementation; would be much better using a priority queue implementation 15 function dijkstra(map, width, height, startpos, searchbackward::Bool) 16 # Initialize our data structures 17 dist = Array{Int32, 2}(undef, height, width) 18 prev = Array{Tuple, 2}(undef, height, width) 19 avail = Set() 20 for row = 1:height 21 for col = 1:width 22 push!(avail, (row, col)) 23 prev[row, col] = () 24 if (row != startpos[1] || col != startpos[2]) 25 dist[row, col] = (height * width) # Greater than max possible distance 26 else 27 dist[row, col] = 0 28 end 29 end 30 end 31 32 while length(avail) > 0 33 next = popmin!(avail, dist) 34 35 # Nothing else is accessible 36 if next == () 37 return (dist, prev) 38 end 39 40 # Find all neighbors of next still in avail 41 for n in [(next[1] - 1, next[2]), (next[1] + 1, next[2]), 42 (next[1], next[2] - 1), (next[1], next[2] + 1)] 43 row = n[1] 44 col = n[2] 45 if row >= 1 && row <= height && col >= 1 && col <= width && in(n, avail) 46 if searchbackward 47 elevationok = (map[n[1]][n[2]] - map[next[1]][next[2]]) >= -1 48 else 49 elevationok = (map[n[1]][n[2]] - map[next[1]][next[2]]) <= 1 50 end 51 if elevationok 52 # There's a path to n from next 53 alt = dist[next[1], next[2]] + 1 54 if alt < dist[n[1], n[2]] 55 dist[n[1], n[2]] = alt 56 prev[n[1], n[2]] = next 57 end 58 end 59 end 60 end 61 end 62 63 return (dist, prev) 64 end 65 66 function dijkstra(map, width, height, startpos, endpos::Tuple) 67 (dist, prev) = dijkstra(map, width, height, startpos, false) 68 69 return dist[endpos[1], endpos[2]] 70 end 71 72 begin 73 map = open("input", "r") do input 74 readlines(input) 75 end 76 mapwidth = length(map[1]) 77 mapheight = length(map) 78 local startrow = local startcol = local endrow = local endcol = 0 79 for row = 1:mapheight 80 for col = 1:mapwidth 81 if map[row][col] == 'S' 82 startrow = row 83 startcol = col 84 rowtochange = map[row] 85 map[row] = rowtochange[1:col - 1] * 'a' * rowtochange[col + 1:end] 86 elseif map[row][col] == 'E' 87 endrow = row 88 endcol = col 89 rowtochange = map[row] 90 map[row] = rowtochange[1:col - 1] * 'z' * rowtochange[col + 1:end] 91 end 92 end 93 end 94 95 dist = dijkstra(map, mapwidth, mapheight, (startrow, startcol), (endrow, endcol)) 96 println("Shortest distance to E (star 1): ", dist) 97 98 (distmatrix, prev) = dijkstra(map, mapwidth, mapheight, (endrow, endcol), true) 99 local mindist = mapwidth * mapheight 100 for row = 1:mapheight 101 for col = 1:mapwidth 102 if map[row][col] == 'a' && distmatrix[row, col] < mindist 103 mindist = distmatrix[row, col] 104 end 105 end 106 end 107 println("Shortest distance to E from any starting point (star 2):", mindist) 108 end