@@ 5,67 5,54 @@ for line in io.lines() do
end
local w, h = #grid[1], #grid
-local function put(self, x, y, d, c)
- local k = x | y << 10 | d << 20
- if not self.seen[k] then
- local t, i = k | c << 21, #self + 1
- while i > 1 do
- local j = i >> 1
- if t > self[j] then break end
- self[i], i = self[j], j
- end
- self[i] = t
- end
+local function enc(x, y, d) return (x - 1) + ((y - 1) * w) << 1 | d end
+local function dec(k)
+ local xy, d = k >> 1, k & 1
+ return xy % w + 1, xy // w + 1, d
end
-local function pop(self)
- local k, h
- repeat
- local t, i = table.remove(self), 1
- if #self == 0 then return t end
- h = self[1]
- repeat
- local j, l, r, s = i, i << 1, (i << 1) + 1, t
- if l <= #self and self[l] < s then i, s = l, self[l] end
- if r <= #self and self[r] < s then i, s = r, self[r] end
- self[j] = s
- until i == j
- k = h & 0x1fffff
- until not self.seen[k]
- self.seen[k] = true
- return h & 0x3ff, h >> 10 & 0x3ff, h >> 20 & 1, h >> 21
+local function remove(queue, c)
+ local t
+ repeat c, t = c + 1, table.remove(queue, 1)
+ until t ~= false
+ if t ~= nil then return c, t end
end
-local function visit(q, x, y, d, cost)
+local queue, seen
+local function visit(x, y, d, cost, add)
if x >= 1 and x <= w and y >= 1 and y <= h then
cost = cost + (string.byte(grid[y], x) - Z)
- if q then put(q, x, y, d, cost) end
+ local k = enc(x, y, d)
+ if add and not seen[k] then
+ local t = queue[cost]
+ if not t then
+ for i = #queue + 1, cost - 1 do queue[i] = false end
+ t = {}
+ queue[cost] = t
+ end
+ t[#t + 1] = k
+ end
end
return cost
end
local function search(min, max)
- local q = {seen={}}
- put(q, 1, 1, H, 0)
- put(q, 1, 1, V, 0)
- for x, y, d, cost in pop, q do
- if x == w and y == h then return cost end
- if d == H then
- local costU, costD = cost, cost
- for dy = 1, min - 1 do
- costU = visit(nil, x, y - dy, V, costU)
- costD = visit(nil, x, y + dy, V, costD)
- end
- for dy = min, max do
- costU = visit(q, x, y - dy, V, costU)
- costD = visit(q, x, y + dy, V, costD)
- end
- else
- local costL, costR = cost, cost
- for dx = 1, min - 1 do
- costL = visit(nil, x - dx, y, H, costL)
- costR = visit(nil, x + dx, y, H, costR)
- end
- for dx = min, max do
- costL = visit(q, x - dx, y, H, costL)
- costR = visit(q, x + dx, y, H, costR)
+ queue, seen = {{enc(1, 1, H), enc(1, 1, V)}}, {}
+ for cost, t in remove, queue, -1 do
+ for _, k in ipairs(t) do
+ if not seen[k] then
+ seen[k] = true
+ local cost1, cost2, x, y, d = 0, 0, dec(k)
+ if x == w and y == h then return cost end
+ d = d ~ 1
+ if d == V then
+ for dy = 1, max do
+ cost1 = visit(x, y - dy, d, cost1, dy >= min)
+ cost2 = visit(x, y + dy, d, cost2, dy >= min)
+ end
+ else
+ for dx = 1, max do
+ cost1 = visit(x - dx, y, d, cost1, dx >= min)
+ cost2 = visit(x + dx, y, d, cost2, dx >= min)
+ end
+ end
end
end
end