/
072-01.cr
47 lines (41 loc) · 1.08 KB
/
072-01.cr
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
record Point, y : Int32, x : Int32 do
Direction = [Point.new(0, 1), Point.new(0, -1), Point.new(1, 0), Point.new(-1, 0)]
def +(other : Point)
Point.new(y + other.y, x + other.x)
end
end
class Solve
getter h : Int32, w : Int32
def initialize
@h, @w = read_line.split.map(&.to_i)
@s = Array(String).new(h) { read_line }
@ans = 0
@start = Point.new(0, 0)
@used = Array(Array(Bool)).new(h) { Array(Bool).new(w, false) }
end
def run
Array.each_product((0...h).to_a, (0...w).to_a) do |(y, x)|
@start = Point.new(y, x)
@used.map(&.fill(false))
@used[y][x] = true
dfs(@start, 0)
end
@ans <= 2 ? -1 : @ans
end
def dfs(p1, cnt) : Nil
(0...4).each do |d|
p2 = p1 + Point::Direction[d]
next unless (0...h).includes?(p2.y) && (0...w).includes?(p2.x) && @s[p2.y][p2.x] == '.'
if @start == p2
@ans = {@ans, cnt + 1}.max
return
end
if !@used[p2.y][p2.x]
@used[p2.y][p2.x] = true
dfs(p2, cnt + 1)
@used[p2.y][p2.x] = false
end
end
end
end
puts Solve.new.run