blob: dcf3ce4bf6db403865b64cb44bf51786bece0474 (
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
70
71
72
73
74
75
76
77
78
79
80
81
82
|
class Node
def initialize(height)
@height = height
@neighbours = []
reset
end
attr_reader :height, :neighbours
attr_accessor :visited, :distance
def add_neighbour(node)
@neighbours << node
end
def reset
@visited = false
@distance = Float::INFINITY
end
end
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
)
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
nodes = grid.flatten
starts = nodes.select { |n| n.height == 1 }
mindist = Float::INFINITY
starts.each { |start|
nodes.each(&:reset)
unvisited = nodes.dup
start.distance = 0
current = start
until goal.visited || current.distance == Float::INFINITY
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
dist = goal.distance
mindist = dist if dist < mindist
}
puts mindist
|
