45 lines
1.1 KiB
Ruby
45 lines
1.1 KiB
Ruby
def count_reachable_positions(matrix)
|
|
get_score_sum(matrix, true)
|
|
end
|
|
|
|
def count_hiking_trails(matrix)
|
|
get_score_sum(matrix, false)
|
|
end
|
|
|
|
def get_score_sum(matrix, skip_visited_cells)
|
|
count = 0
|
|
|
|
for i in 0...matrix.length do
|
|
for j in 0...matrix[0].length do
|
|
next if matrix[i][j] != 0
|
|
|
|
count += bfs(matrix, i, j, skip_visited_cells)
|
|
end
|
|
end
|
|
|
|
count
|
|
end
|
|
|
|
def bfs(matrix, i, j, skip_visited_cells)
|
|
visits = Array.new(matrix.length) { Array.new(matrix[0].length, false) }
|
|
queue = [[i, j]]
|
|
matches = 0
|
|
|
|
until queue.empty?
|
|
i, j = queue.pop
|
|
next if skip_visited_cells && visits[i][j]
|
|
|
|
visits[i][j] = true
|
|
if matrix[i][j] == 9
|
|
matches += 1
|
|
next
|
|
end
|
|
|
|
queue.unshift([i - 1, j]) if i > 0 && matrix[i - 1][j] == matrix[i][j] + 1
|
|
queue.unshift([i + 1, j]) if i < matrix.length - 1 && matrix[i + 1][j] == matrix[i][j] + 1
|
|
queue.unshift([i, j - 1]) if j > 0 && matrix[i][j - 1] == matrix[i][j] + 1
|
|
queue.unshift([i, j + 1]) if j < matrix[0].length - 1 && matrix[i][j + 1] == matrix[i][j] + 1
|
|
end
|
|
|
|
matches
|
|
end
|