Как посчитать количество и типы кораблей в матрице по правилам морского боя?

Что проверяют

Умеете ли вы превратить игровые правила в чёткий алгоритм обхода матрицы и не забыть про границы. После решения обычно просят оценить сложность и спрашивают, как проверить, что расстановка вообще корректна.

Как отвечать

Начните с уточнений: поле int[][] или char[][], где 1 это палуба; корабли прямые, горизонтальные или вертикальные; по классическим правилам не касаются друг друга даже углами. Можно ли менять входной массив? От ответа зависит, нужен ли отдельный boolean[][] visited.

Дальше два рабочих подхода:

• поиск начала корабля: клетка с палубой считается началом, если слева и сверху от неё вода или край поля. От неё идёте вправо или вниз и считаете длину. Каждый корабль посчитан ровно один раз, лишняя память не нужна;
• обход компонент связности: BFS или DFS от каждой непосещённой палубы с отметкой в visited. Универсальнее и заодно проверяет форму: если все клетки компоненты лежат в одной строке или в одном столбце, это корабль, иначе расстановка ошибочна.

Результат удобно хранить в int[] counts, где индекс равен длине, или в Map<Integer, Integer>. Для проверки по правилам сравните с эталоном: четыре однопалубных, три двухпалубных, два трёхпалубных и один четырёхпалубный. Касание углами ловится проверкой диагональных соседей каждой палубы.

Сложность O(n·m) по времени в обоих вариантах. Рекурсивный DFS на поле 10×10 безопасен, но на большой матрице лучше итеративный обход через ArrayDeque, иначе можно получить StackOverflowError.

Где спотыкаются

Считают палубы вместо кораблей или обходят во все четыре стороны без проверки формы. Тогда фигура буквой «Г» из четырёх клеток засчитывается как четырёхпалубный корабль.

Выходят за границы массива при проверке соседей. Проверку индексов нужно делать до обращения к field[i][j], а не после, иначе первая же палуба у края даст ArrayIndexOutOfBoundsException.

Пишут отдельный if на каждую длину и забывают про корабли длиннее двух палуб. Массив счётчиков по длине убирает эту ветвистость и работает для любого набора кораблей.