You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
75 lines
2.0 KiB
75 lines
2.0 KiB
4 years ago
|
width = nil
|
||
|
|
map = {}
|
||
|
|
for line in io.lines(arg[1]) do
|
||
|
|
if not width then
|
||
|
|
width = #line
|
||
|
|
end
|
||
|
|
for char in line:gmatch(".") do
|
||
|
|
table.insert(map, char)
|
||
|
|
end
|
||
|
|
end
|
||
|
|
|
||
|
|
function reachable_keys(map, pos_y, pos_x, keys, dist)
|
||
|
|
local cell = map[width * pos_y + pos_x]
|
||
|
|
if cell == "@" then
|
||
|
|
cell = "."
|
||
|
|
end
|
||
|
|
if cell == "." then
|
||
|
|
map[width * pos_y + pos_x] = "#"
|
||
|
|
reachable_keys(map, pos_y + 1, pos_x, keys, dist + 1)
|
||
|
|
reachable_keys(map, pos_y - 1, pos_x, keys, dist + 1)
|
||
|
|
reachable_keys(map, pos_y, pos_x + 1, keys, dist + 1)
|
||
|
|
reachable_keys(map, pos_y, pos_x - 1, keys, dist + 1)
|
||
|
|
elseif string.byte(cell) >= 97 and string.byte(cell) <= 122 then
|
||
|
|
table.insert(keys, {key=cell, y=pos_y, x=pos_x, dist=dist})
|
||
|
|
end
|
||
|
|
return keys
|
||
|
|
end
|
||
|
|
|
||
|
|
function find_paths(map, pos_y, pos_x)
|
||
|
|
local keys = reachable_keys({table.unpack(map)}, pos_y, pos_x, {}, 0)
|
||
|
|
local paths = {}
|
||
|
|
for _, key in ipairs(keys) do
|
||
|
|
--print(key.key, key.dist)
|
||
|
|
local open_map = {table.unpack(map)}
|
||
|
|
open_map[width * pos_y + pos_x] = "."
|
||
|
|
open_map[width * key.y + key.x] = "@"
|
||
|
|
for i, x in ipairs(open_map) do
|
||
|
|
if x:lower() == key.key then
|
||
|
|
open_map[i] = "."
|
||
|
|
break
|
||
|
|
end
|
||
|
|
end
|
||
|
|
local path = find_paths(open_map, key.y, key.x)
|
||
|
|
if #path == 0 then
|
||
|
|
table.insert(paths, {path={key.key}, dist=key.dist})
|
||
|
|
else
|
||
|
|
for _, p in ipairs(path) do
|
||
|
|
table.insert(p.path, key.key)
|
||
|
|
p.dist = p.dist + key.dist
|
||
|
|
table.insert(paths, p)
|
||
|
|
end
|
||
|
|
end
|
||
|
|
end
|
||
|
|
return paths
|
||
|
|
end
|
||
|
|
|
||
|
|
pos_y = nil
|
||
|
|
pos_x = nil
|
||
|
|
for i, x in ipairs(map) do
|
||
|
|
if x == "@" then
|
||
|
|
pos_y = i // width
|
||
|
|
pos_x = i % width
|
||
|
|
break
|
||
|
|
end
|
||
|
|
end
|
||
|
|
|
||
|
|
paths = find_paths(map, pos_y, pos_x)
|
||
|
|
smallest = nil
|
||
|
|
for _, path in ipairs(paths) do
|
||
|
|
if not smallest or smallest.dist > path.dist then
|
||
|
|
smallest = path
|
||
|
|
end
|
||
|
|
end
|
||
|
|
print(table.concat(smallest.path, ","), smallest.dist)
|