Левая кнопка мыши
Левая кнопка мыши
Минер является довольно популярной игрой в операционной системе Windows. Цель игры заключается в поиске мин и маркировании их положения. Вы размещате щелчком правой кнопки мыши небольшой флаг в клетке, в котрой по Вашему мнению расположена мина. Щелчком левой кнопки мыши можно открыть клетку, в которой по Вашему мнению мины нет. Если в этом квадрате все-таки расположена мина, то она взрывается и Вы проигрываете. В противном случае есть два варианта. В первом случае открывается число от 1 до 8, показывающее суммарное количество мин, окружающих данную клетку. Например, если Вы нажали левую кнопку мыши и в квадрате высветилось число 8, то это означает, что данная клетка окружена 8 клетками с минами, т.е все 8 соседних клеток содержат мины. Во втором случае, если вокруг этой клетки нет соседних мин, то кроме этой клетки открываются и все соседние. Если в каких-то из соседних клеток также нет окружающих мин, то процесс открытия соседних клеток продолжается. То есть фактически компьютер помогает Вам открыть все свободные от мин соседние клетки. Цель игры состоит в открыти всех свободных от мин клеток. Том очень увлеается этой игрой, но к сожалению его правая кнопка мыши повреждена и он может пользоваться только левой кнопкой мыши. Для того чтобы избежать возможного дальнейшего повреждения мыши он хочет закончить игру нажав на левую кнопку мыши минимальное количество раз. Зная начальное положение в игре Вам необходимо определить это самое минимальное количество нажатий левой кнопкой мыши.
Входные данные
Первая строка содержит целое число, указывающее количество тестовых случаев T (T ≤ 12). Каждый тестовый случай начинается строкой, содержащей целое число n (5 ≤ n ≤ 9) - размер минного поля n×n. Каждая из последующих n строк содержит по n символов M_{ij }(1 ≤ i, j ≤ n), M_ij обозначает текущий статус клетки в строке i и столбце j, где '@' обозначает мину, '0-8' обознают сумарные количества мин в прилегающих клетках, цифрой '0' обозначены клетки, по соседству с которыми мин нет. Гарантируется, что все положения корректны.
Выходные данные
Для каждого тестового случая в отдельной строке вывести сообщение о номере теста (начиная с 1) и далее минимальное количество нажатий левой кнопки мыши (см. пример выходных данных).
Пример
1 9 001@11@10 001111110 001111110 001@22@10 0012@2110 221222011 @@11@112@ 2211111@2 000000111
Case 1: 24