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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
-- Calculates shortest path of Knight from (1, 1) to (x, y).
-- Prints matrix of shortest paths for all cells.
-- Knight can't leave the rectangle from (1, 1) to (x, y).
-- See https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
-- See http://stackoverflow.com/questions/2339101
-- Usage:
-- $ lua knight_dijkstra.lua X Y
local binaryheap = require 'binaryheap'
local ROWS = tonumber(arg[2]) or 8
local COLS = tonumber(arg[1]) or 8
local unvisited = binaryheap.minUnique()
local function Cell(x, y)
return x .. '_' .. y
end
local function Coordinates(cell)
local x, y = cell:match('(%d+)_(%d+)')
return x, y
end
local function neighbours(cell)
local x, y = Coordinates(cell)
local gen = coroutine.wrap(function()
coroutine.yield(x - 1, y - 2)
coroutine.yield(x - 1, y + 2)
coroutine.yield(x + 1, y - 2)
coroutine.yield(x + 1, y + 2)
coroutine.yield(x - 2, y - 1)
coroutine.yield(x - 2, y + 1)
coroutine.yield(x + 2, y - 1)
coroutine.yield(x + 2, y + 1)
end)
return coroutine.wrap(function()
for xx, yy in gen do
if 1 <= xx and xx <= COLS and
1 <= yy and yy <= ROWS then
coroutine.yield(Cell(xx, yy))
end
end
end)
end
for y = 1, ROWS do
for x = 1, COLS do
local cell = Cell(x, y)
unvisited:insert(math.huge, cell)
end
end
unvisited:update('1_1', 0)
local final_distance = {}
while unvisited:peek() do
local current_distance, current = unvisited:peek()
assert(not final_distance[current])
final_distance[current] = current_distance
unvisited:remove(current)
-- update neighbours
local new_distance = current_distance + 1
for neighbour in neighbours(current) do
if unvisited.reverse[neighbour] then
local pos = unvisited.reverse[neighbour]
local distance = unvisited.value[pos]
if distance > new_distance then
unvisited:update(neighbour, new_distance)
end
end
end
end
for y = 1, ROWS do
local row = {}
for x = 1, COLS do
local cell = Cell(x, y)
local distance = final_distance[cell]
table.insert(row, distance)
end
print(table.concat(row, ' '))
end
|
