В маленьком городке имеется домов, индексированных парами чисел
для . Дома с индексами , назовем
соседними, если . В момент времени 0, в доме с индексом ,
где , начался пожар. В течение каждого последующего
временного интервала пожарники ставят систему защиты от пожара
одному дому, до которого огонь еще не добрался, в то время как пожар
распространяется на все незащищенные дома, каждый из которых соседствуют
с некоторым домом, охваченным пожаром в момент времени . Дом,
где установлена система защиты от пожара, не горит. Процесс завершается,
когда распространение пожара становится невозможным. Какое максимальное
число домов могут спасти пожарники?
Замечание.
Можно считать, что городок имеет форму таблицы , где дома
суть единичные клетки, — индекс дома, стоящего в левом верхнем углу,
и указывают соответственно строку и столбец дома с индексом .