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
|
#!/usr/bin/env lua
local heights = {}
for i = string.byte('a'),string.byte('z') do
heights[string.char(i)] = i - string.byte('a')
end
heights.S, heights.E = heights.a, heights.z
local map = {}
local start, endpos
for line in io.lines() do
map[#map+1] = {}
for char in line:gmatch("(.)") do
table.insert(map[#map],{height = heights[char], wts = math.huge})
if char == "S" then
start = {#map,#map[#map]}
map[#map][#map[#map]].wts = 0
elseif char == "E" then
endpos = {#map,#map[#map]}
end
end
end
local adjacents = {{-1,0},{1,0},{0,-1},{0,1}} -- up, down, left, right
local seen,unseen = {},{start}
while #unseen > 0 do
local vertex = table.remove(unseen,1)
local data = map[vertex[1]][vertex[2]]
for _, offset in pairs(adjacents) do
local row,col = vertex[1] + offset[1], vertex[2] + offset[2]
if map[row] and map[row][col] and (map[row][col].height <= data.height + 1) then
local adata = map[row][col]
if adata.wts > data.wts + 1 then
adata.wts = data.wts + 1
table.insert(unseen,{row,col})
end
end
end
end
print(map[endpos[1]][endpos[2]].wts)
|
