Капитан Q`s Сокровище
У вас есть старая карта, нарисованная печально известным пиратом "Капитаном Q". Она показывает расположение множества сундуков с сокровищами, зарытых на острове.
Карта разделена на квадратные участки, каждый из которых может содержать цифру или быть пустым. Цифра обозначает количество сундуков в 9 соседних участках (включая сам участок и его 8 соседей). Предполагается, что в каждом участке может быть не более одного сундука.
Хотя у вас есть карта, вы не можете точно определить, где зарыты сундуки. Даже общее количество сундуков на острове неизвестно. Однако можно вычислить минимальное количество сундуков, зарытых на острове. Ваша задача — написать программу, которая определяет это количество.
Входные данные
Входные данные состоят из нескольких наборов. Каждый набор данных имеет следующий формат.
h wmap
Первая строка набора данных содержит два положительных целых числа h и w. h — это высота карты, а w — это ширина карты. Предполагается, что 1 ≤ h ≤ 15 и 1 ≤ w ≤ 15.
Следующие h строк представляют карту. Каждая строка состоит из w символов и соответствует горизонтальной полосе карты. Каждый символ в строке описывает состояние участка следующим образом.
'.': Участок не является частью острова (вода). Здесь нет сундука.
'*': Участок является частью острова, и количество сундуков в его 9 соседях неизвестно.
'0'-'9': Участок является частью острова, и цифра обозначает количество сундуков в его 9 соседях.
Предполагается, что карта не содержит противоречий, то есть существует по крайней мере одно возможное расположение сундуков. Также предполагается, что количество участков с цифрами составляет как минимум один и не более 15.
Строка с двумя нулями указывает на конец ввода.
Выходные данные
Для каждого набора данных выведите строку, содержащую минимальное количество сундуков. Вывод не должен содержать никаких других символов.