Затопи-Это
Flood-It — популярная игра для одного игрока на многих смартфонах. Игроку предоставляется доска размером n×n с плитками, где каждая плитка имеет один из 6 цветов (пронумерованных от 1 до 6). Каждая плитка соединена с максимум 4 соседними плитками в направлениях Север, Юг, Восток и Запад. Плитка считается соединенной с начальной (верхний левый угол), если она того же цвета и существует путь к начальной плитке, состоящий только из плиток этого цвета.
Игрок делает ход, выбирая один из 6 цветов. После выбора все плитки, соединенные с начальной, изменяются на выбранный цвет. Игра продолжается до тех пор, пока все плитки не станут одного цвета. Цель игры — изменить все плитки на один цвет, желательно с минимальным количеством ходов.
Доказано, что нахождение оптимальных ходов — очень сложная задача. Для этой задачи вы будете моделировать простую жадную стратегию, чтобы оценить её эффективность:
для каждого хода выбирайте цвет, который приведет к наибольшему количеству плиток, соединенных с начальной;
если есть равенство, выбирайте цвет с наименьшим номером.
Чтобы проиллюстрировать это, рассмотрим первый тестовый случай из примера ввода, исходная доска выглядит так:
Если мы выберем цвет 3 для первого хода, результат будет таким:
где плитки, соединенные с начальной, заштрихованы. В следующем ходе мы выбираем цвет 4, потому что можем увеличить количество плиток, соединенных с начальной, на 5 плиток:
Входные данные
Входные данные состоят из нескольких тестовых случаев. Первая строка ввода — это одно целое число, не более 20, указывающее количество тестовых случаев, которые следуют. Каждый случай начинается со строки, содержащей целое число n (1 ≤ n ≤ 20). Следующие n строк содержат по n символов, задающих начальные цвета плиток на доске размером n×n. Каждый цвет указан цифрой от 1 до 6.
Выходные данные
Для каждого случая выведите две строки вывода. Первая строка указывает количество ходов, необходимых для изменения всех плиток на один цвет. Вторая строка указывает 6 целых чисел, разделенных одним пробелом. i-е целое число указывает количество раз, когда цвет i выбирается в качестве хода в игре.