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