Задача 30: Считаем кораблики
На клетчатом листе бумаги размера M*N нарисованы корабли. Каждый
корабль представляет собой вертикальный или горизонтальный набор
подряд идущих закрашенных клеток, разные корабли не соприкасаются по
сторонам или углам и не накладываются друг на друга. В отличие от
обычного "Морского боя" могут быть корабли более, чем из четырех
клеток. Необходимо найти число кораблей.
Пример: лист - 12*12, кораблей - 7.
Формат входных данных
Входной файл INPUT.TXT содержит в первой строке два целых числа,
разделенные пробелом, - размеры листа бумаги M и N, 2 <= M, N <=
100. Далее идет таблица из M строк по N целых чисел, разделенных
пробелами, состоящая из 0 или 1 (0 - если клетка пустая, 1 - если
она входит в состав какого-то корабля), одна строка таблицы
располагается в одной строке файла.
Пример:
12 12
0 0 0 0 0 0 0 0 0 0 0 1
0 1 1 1 1 1 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0 0 0 1
0 1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0
0 1 0 1 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0
Формат выходных данных
Выходной файл OUTPUT.TXT должен содержать число (целое) кораблей
на листе.
Пример:
7
Решение:
В этой задаче нам понадобиться все кораблики "утопить". На самом
деле решение простое:
Идем от левого верхнего угла по строкам (сначала просматриваем
первую строку, затем вторую и т.д.). В случае если нашли "1" (кусок
корабля), то увеличиваем счетчик на 1, а кораблик топим. Я топил
кораблики рекурсивно, хотя здесь можно было сделать это без
рекурсии, потому как кораблики не гнутые. Но с рекурсией короче и
универсальнее.
У нас есть координата одного сегмента корабля и знание о том, что
выше и левее от него никого нет, т.е. от этого сегмента кораблик
может идти только вправо или вниз. "Утопим" этот сегмент
корабля(т.е. присвоим этой клетки значение, отличное от 1).
Проверим, если клетка правее содержит в себе сегмент кораблика, то
нашлем на нее нашу рекурсивную процедуру-убийцу(не увеличивая
счетчик - кораблик то один и тот же). Точно также поступим, если
клетка снизу от нашего сегмента занята корабликом. В итоге весь
кораблик будет иметь статус утопленного, и мы можем смело смотреть
наше поле дальше, в поиске следующих жертв маньячной процедуры (всех
кого найдет - утопит, только если этот кораблик не авианосец в форме
перевернутой буквы "П", но их в этой игре вроде бы нет, да и
исправить процедуры несложно :).
Домашнее задание: написать систему спутникового наведения
ракет на ВМФ потенциального противника ;).
Далее
ð
