blob: cc58d7d437accdb0e581076ebb6746ef63145e97 (
plain)
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
|
class Node
def initialize(height)
@height = height
@neighbours = []
@visited = false
@distance = Float::INFINITY
end
attr_reader :height, :neighbours
attr_accessor :visited, :distance
def add_neighbour(node)
@neighbours << node
end
end
start = nil
goal = nil
grid = $stdin.readlines.map do |line|
line.strip.chars.map do |ch|
n = Node.new(
case ch
when ?a..?z
ch.ord - 96
when ?S
1
when ?E
26
end
)
start = n if ch == ?S
goal = n if ch == ?E
n
end
end
h = grid.length
w = grid[0].length
h.times.each do |rix|
w.times.each do |cix|
grid[rix][cix].add_neighbour(grid[rix-1][cix]) if rix - 1 >= 0
grid[rix][cix].add_neighbour(grid[rix][cix-1]) if cix - 1 >= 0
grid[rix][cix].add_neighbour(grid[rix+1][cix]) if rix + 1 < h
grid[rix][cix].add_neighbour(grid[rix][cix+1]) if cix + 1 < w
end
end
unvisited = grid.flatten
start.distance = 0
current = start
until goal.visited
current.neighbours.select { |n|
!n.visited &&
(n.height - current.height) < 2
}.each { |n|
d = current.distance + 1
n.distance = d if d < n.distance
}
current.visited = true
unvisited.delete(current)
current = unvisited.min{|a, b| a.distance <=> b.distance}
end
puts goal.distance
|
