94 lines
1.9 KiB
Nim
94 lines
1.9 KiB
Nim
import system/io
|
|
import strutils
|
|
import sequtils
|
|
import tables
|
|
import sugar
|
|
|
|
const
|
|
SYM_START = 'S'
|
|
SYM_END = 'E'
|
|
SYM_LOWEST = 'a'
|
|
|
|
type
|
|
Coords = tuple
|
|
x, y: int
|
|
|
|
proc diff(a, b: int): int =
|
|
if a > b: a - b
|
|
else: b - a
|
|
|
|
proc height(i: char): int =
|
|
(
|
|
case i:
|
|
of SYM_START:
|
|
'a'
|
|
of SYM_END:
|
|
'z'
|
|
else:
|
|
i
|
|
).ord
|
|
|
|
var startPoint: Coords
|
|
var endPoint: Coords
|
|
var lowestPoints = newSeq[Coords]()
|
|
var adjacents = initTable[Coords, seq[Coords]]()
|
|
|
|
let heightMap = collect(
|
|
for line in stdin.readAll.split:
|
|
if line != "": line
|
|
)
|
|
|
|
for x in 0 .. heightMap.len - 1:
|
|
for y in 0 .. heightMap[x].len - 1:
|
|
var adjs = newSeq[Coords](0)
|
|
|
|
let h = heightMap[x][y].height
|
|
|
|
case heightMap[x][y]:
|
|
of SYM_START:
|
|
startPoint = (x, y)
|
|
of SYM_END:
|
|
endPoint = (x, y)
|
|
of SYM_LOWEST:
|
|
lowestPoints.add((x, y))
|
|
else: discard
|
|
|
|
if y > 0 and h - heightMap[x][y - 1].height < 2:
|
|
adjs.add((x, y - 1))
|
|
if y < heightMap[x].len - 1 and h - heightMap[x][y + 1].height < 2:
|
|
adjs.add((x, y + 1))
|
|
if x > 0 and h - heightMap[x - 1][y].height < 2:
|
|
adjs.add((x - 1, y))
|
|
if x < heightMap.len - 1 and h - heightMap[x + 1][y].height < 2:
|
|
adjs.add((x + 1, y))
|
|
|
|
adjacents[(x, y)] = adjs
|
|
|
|
var unvisited = adjacents.keys.toSeq
|
|
var shortest = collect(initTable()):
|
|
for node in unvisited:
|
|
{node: high(int) - 1}
|
|
|
|
shortest[endPoint] = 0
|
|
|
|
while unvisited.len != 0:
|
|
var current_min: Coords = (-1, -1)
|
|
|
|
for node in unvisited:
|
|
if current_min.x == -1 or shortest[node] < shortest[current_min]:
|
|
current_min = node
|
|
|
|
for adj in adjacents[current_min]:
|
|
let t = shortest[current_min] + 1
|
|
if t < shortest[adj]:
|
|
shortest[adj] = t
|
|
|
|
unvisited.del(unvisited.find(current_min))
|
|
|
|
var min = high(int)
|
|
for node in lowestPoints:
|
|
if shortest[node] < min:
|
|
min = shortest[node]
|
|
|
|
echo min
|