Представим лес Берляндии как бесконечное клеточное поле. В каждой клетке растет дерево. Или росло, до недавних событий.

Разрушительный огонь бушевал в лесу и уничтожил несколько деревьев. У вас есть прямоугольная карта $$$n \times m$$$, которая описывает поврежденную часть леса. Сожженные деревья отмечены на карте как «X», в то время как остальные отмечены как «.». Вы можете быть уверены, что все поврежденные деревья отмечены на карте. Все деревья за пределами карты — не повреждены.

Пожарные быстро потушили огонь, и теперь расследуют данный инцидент. Основная версия — это поджог: в какой-то момент времени (примем этот момент за $$$0$$$) несколько деревьев были подожжены. В начале минуты $$$0$$$ горели только подожженные деревья. В конце каждой минуты огонь распространяется от горящего дерева к $$$8$$$ соседним к нему деревьям. В начале минуты $$$T$$$ огонь был потушен.

Пожарные хотят найти поджигателей так быстро как это возможно. Но проблема в том, что они не знают ни значение $$$T$$$ (как долго бушевал пожар), ни местоположение деревьев, которые были подожжены. Они хотят, чтобы вы определили максимальное значение $$$T$$$ (чтобы узнать, сколько времени в запасе у поджигателей) и возможное множество деревьев, которые были подожжены.

Заметим, что вы хотите максимизировать значение $$$T$$$, но множество деревьев может быть произвольным.