Морской бой
Задача: дано игровое поле, которое задано матрицей m x n, где каждая ячейка представляет собой клетку корабля «X» или пустую клетку «.».
Необходимо найти количество всех кораблей на игровом поле.
Примечание: корабли можно размещать на игровом поле только горизонтально или вертикально. Также по крайней мере, 1 горизонтальная или вертикальная клетка разделяет два корабля.
Входные данные: board — символьная матрица, содержащая символы ‘.’, ‘X’. Размер сторон матрицы от 1 до 100.
Вывод: количество всех кораблей
Пример:
Board = [
[‘X’, ‘.’, ‘.’, ‘X’],
[‘.’, ‘.’, ‘.’, ‘X’],
[‘.’, ‘.’, ‘.’, ‘X’]]
Output: 2
Разбор
Первый способ решения — это запустить поиск в глубину (DFS), пометить посещенные клетки корабля и посчитать общее количество кораблей. Поиск в глубину довольно дорогой метод по времени, также он использует рекурсию.
Чтобы избежать этого, мы можем оптимизировать наш алгоритм, используя тот, факт, что корабли могут распологаться только по горизонтали или только по вертикали. Т.е. нам нужно посчитать только первые клетки кораблей.
Если на очередном шаге мы встретили клетку корабля, мы проверяем предыдущую клетку по вертикали и по горизонатли, если там также находится клетка корабля, то мы пропускаем эту итерацию. Так как мы уже посчитали этот корабль раньше.
Если же на очередном шаге мы встретили клетку корабля и предыдушие клетки по горизонтали и вертикали не являются клетками корабля, то значит мы нашли 1ю клетку нового корабля. В этом случае увеличиваем наш результирующий счетчик.
Детали смотрите в коде.
Реализация
https://gist.github.com/unilecs/1d63a9881b198e059eee7d7b72539399
