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

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

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

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

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

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

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

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

Пример:

battle.inbattle.out
3 5 0 0 0 1 0 0 0 0 1 0 1 1 0 1 12


Source: Petrozavodsk Winter 2003. Take-Off, Monday, February 03

Discuss       Submit a solution



Printable version