0058. Обобщенный морской бой

Имя входного файла:	battle.in
Имя выходного файла:	battle.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

В игре <<обобщенный морской бой>> корабль на доске m*n представляет собой вертикально или горизонтально ориентированный прямоугольник, ширина которого – одна клетка, а длина произвольна. Кораблей может быть произвольное количество, они могут пересекаться или примыкать один к другому произвольным образом.

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

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

Первая строка исходных данных задачи – размерность матрицы 1≤ m, n≤ 100, последуюшие m строк состоят их n нулей и единиц, единица соответствует занятой кораблем клетке, нули – клеткам, про которые неизвестно, принадлежат они какому-либо кораблю или нет.

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

Результат вычислений – искомое наименьшее количество кораблей.

Пример:

battle.in	battle.out
3 5 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1	2

Источник: Petrozavodsk Winter 2003. Take-Off, Monday, February 03

Обсудить       Отправить решение