Задача номер 5. Тушение пожара

5. Тушение пожара

На прямоугольном поле, которое размечено на квадратные делянки, произошло возгорание. В вашем распоряжении имеется карта, на которой представлены делянки двух видов – мокрые и сухие. Те делянки, на которых посевы мокрые и гореть не могут, обозначены символом ‘#’, сухие делянки обозначены цифрой ноль. Место возгорания обозначено буквой ‘F’. Огонь распространяется по сухим делянкам, имеющим общие границы по вертикали или горизонтали. В вашем распоряжении находится пожарный вертолет. Вы можете совершить на нем только один вылет и сбросить воду на одну из сухих делянок. В зону возгорания вертолет по технике безопасности лететь не может.
Нужно определить, какое максимальное количество сухих делянок можно спасти от огня, если использовать один вылет пожарного вертолета. Другими словами, нужно посчитать количество сухих делянок, куда огонь не сможет добраться после того, как на одну из них будет вылита вода из вертолета. Делянку, на которую будет вылита вода, тоже считать, как спасенную.

Входные данные

В первой строке входного файла записаны через пробел два натуральных числа N и M. Число N – количество строк карты, M — количество символов в каждой строке. Далее в N строках располагается карта поля. Числа N и M могут принимать значения от 1 до 1000 включительно. На карте символ 'F' всегда присутствует, и только один.

Выходные данные

В выходной файл необходимо вывести одно целое число — максимальное количество сухих делянок, которые можно спасти от огня.

Примеры

input.txt
4 6
F000#0
0####0
00#000
000000
1 6
00F000
2 5
00#0F
00000
3 3
000
0F0
000

output.txt
14
3
6
1

Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по памяти: 64 Мб
Ограничение по времени: 1 секунда на тест
Максимальная оценка за задачу: 210 баллов

Соревнование: Всесибирская открытая олимпиада по информатике 2010
Источник: http://olimpic.nsu.ru
Сдать решение: Форма отправки