Национальные сокровища
Великий зал национального музея недавно несколько раз подвергался ограблениям, что вызвало обеспокоенность за безопасность выставленных сокровищ. Чтобы обеспечить защиту зала, музей заключил контракт с частной охранной компанией на предоставление дополнительных охранников, которые будут находиться в большом зале и следить за древними артефактами. Музей стремится нанять минимальное количество дополнительных охранников для обеспечения безопасности большого зала.
Большой зал представлен в виде двумерной сетки размером RxC ячеек. Некоторые ячейки уже заняты охранниками музея. Все остальные ячейки содержат артефакты различных типов (статуи, скульптуры и т.д.), которые могут быть заменены новыми нанятыми охранниками. Для каждого артефакта определены несколько других ячеек в зале как критические точки артефакта, в зависимости от его ценности, типа хранилища и других факторов. Это означает, что если артефакт остается в зале, то на всех его критических точках должны стоять охранники. Охранник, стоящий в критической точке нескольких артефактов, может следить за всеми ними. Однако охранник не может стоять в ячейке, содержащей артефакт (вместо этого артефакт можно удалить, чтобы позволить охраннику занять это место). Также нельзя удалить артефакт и оставить пространство пустым (можно только заменить артефакт новым нанятым охранником).
Изучив все артефакты в большом зале, вы выяснили, что критические точки любого артефакта (отмечены ) всегда являются подмножеством 12 соседних ячеек, как показано на сетке ниже.
Соответственно, тип артефакта может быть указан как неотрицательное целое число, где i-й бит равен 1, только если критическая точка номер i из приведенного выше рисунка является критической точкой этого артефакта. Например, артефакт типа 595 (в двоичной системе 1001010011) может быть изображен, как показано на рисунке ниже. Обратите внимание, что биты нумеруются справа налево (самый правый бит — это бит номер 1). Если критическая точка артефакта находится за пределами сетки зала, она считается защищенной.
Вам дана планировка большого зала, и вас просят найти минимальное количество дополнительных охранников, которых нужно нанять, чтобы все оставшиеся артефакты были защищены.
Входные данные
Ваша программа будет тестироваться на одном или нескольких тестовых случаях. Каждый тестовый случай задается с помощью R+1 строк. Первая строка задает два целых числа (1 ≤ R, C ≤ 50), которые являются размерами зала музея. Следующие R строк содержат C целых чисел, разделенных одним или несколькими пробелами. j-е целое число в i-й строке равно -1, если ячейка (i, j) уже содержит одного из охранников музея, в противном случае она содержит целое число (0 ≤ T < 2^12), представляющее тип артефакта в этой ячейке.
Последняя строка входного файла содержит два нуля.
Выходные данные
Для каждого тестового случая выведите следующую строку: k. G
Где k — номер тестового случая (начиная с единицы), а G — минимальное количество дополнительных охранников, которых нужно нанять, чтобы все оставшиеся артефакты были защищены.
На рисунке справа показано решение второго тестового случая, где два артефакта в центре заменены охранниками.