0037. Бомба

Input file name:	bomb.in
Output file name:	bomb.out
Time limit:	2 s
Memory limit:	64 megabytes

В одном районе г. Петрозаводска строители, разбирая развалины старого дома, для того, чтобы построить новый, наткнулись на странную груду стен, которая мешала им. Пришлось вызвать эксперта по разборке завалов. Но и он не помог. Как позже выяснилось (с помощью саперов), эти стены скрывали одну штуку, представляющую собой, не что иное, как бомбу, которая могла в любой момент взорваться. Скорей всего, подобного рода ситуация могла сложиться только с тем учетом, что в данном месте когда-то проходили боевые события. На исторической кафедре ПетрГУ выяснили, что эта бомба где-то 42 года изготовления. "Ну да, так и есть" – сказал саперам Савицкий, перебирая летописи. Но как бы там ни было, инструкций по эксплуатированию данной бомбы не нашлось, и саперам ничего не остается, кроме как, вывести бомбу за пределы города и взорвать. Химики посчитали, исходя из размеров бомбы, что она эквивалентна 1000 кг тротила. А это эквивалентно яме размером 60 х 60 км и глубиной 1000 м на месте города Петрозаводска.

Завал представляет собой прямоугольник размером , состоящий из единичных квадратиков. Завал разделен на K стен (2 ≤ K ≤ 100). Каждая стена представляет собой связное множество квадратиков, т.е. из каждого квадратика стены можно дойти до любого другого ее квадратика, при этом разрешается переходить с квадратика на квадратик, только если они имеют общую сторону (общей вершины недостаточно). В завале нет вершины, которая граничила бы более чем с тремя стенами (т.е. четыре квадратика, имеющие общую вершину, не могут принадлежать четырем разным стенам).

Следует отметить, что эта бомба очень чувствительна, и для того, чтобы ее вывести, необходимо для начала разобрать все стены, с которыми она граничит. При том нельзя начинать разбирать с середины, следует последовательно снимать стены, начиная с граничных, углубляясь внутрь. Две стены граничат, если существует два квадратика, имеющие общую сторону, один из которых принадлежит первой из них, а другой – второй. Каждая стена имеет свой символ. Бомба обозначена символом ╓ (ASCII-код 253). Стена называется граничной, если она содержит граничные квадратики. Бомба не содержит граничные квадратики. Но исходя из того, что бомба не имеет нормальной геометрической формы, стена может также находиться внутри ее.

Чтобы снять стену, надо чтобы выполнялось одно из двух условий: либо она граничная, либо она граничит с какой-либо уже снятой стеной.

Нужно быть очень осторожными, и поэтому следует снять как можно меньше стен.

Формат входного файла

Первая строка файла содержит M и N (3 ≤ M, N ≤ 200). Следующие M строк содержат N символов каждая и задают карту завала. Символ, находящийся в i+1-й строке входного файла на j-м месте, представляет собой символ стены, которой принадлежит квадратик (i,═j). Все символы имеют ASCII-код больше 32 (пробела).

Формат выходного файла

Выведите в выходной файл единственное число – количество стен, которые требуется снять. Если разобрать завал невозможно, выведите (без кавычек) Explosion : hole instead of Petrozavodsk

Пример:

bomb.in	bomb.out
5 6 111116 122216 12╓446 133346 555556	4

Source: Petrozavodsk training camp, Summer 2002. DNK contest
Author: Denis Davydov (DNK team)

Discuss       Submit a solution