Как определить, что корабль уже обработан при обходе матрицы?

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

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

Как отвечать

Корабль это связная область клеток, и при обходе нужно помнить, какие клетки уже отнесены к найденному кораблю. Варианты:

• массив boolean[][] visited: той же размерности, что поле. Нашли непосещённую клетку корабля, увеличили счётчик и заливкой (DFS или BFS) пометили весь корабль. Память O(n·m), вход не меняется;
• метка в самой матрице: посещённую клетку перезаписываете, например 'X' на '.'. Экономит память, но портит вход, это стоит проговорить с интервьюером;
• без пометок: если корабли прямые и не касаются друг друга, как в «Морском бое», корабль считается по первой клетке. Клетка является началом, если сверху и слева нет палубы: board[i][j] == 'X' && (i == 0 || board[i-1][j] != 'X') && (j == 0 || board[i][j-1] != 'X'). Один проход, O(1) памяти.

Для заливки в Java надёжнее итеративный BFS через ArrayDeque<int[]>: рекурсивный DFS по сплошной области на поле 1000 на 1000 упадёт с StackOverflowError. Если соседство считается и по диагонали, уточните это заранее и добавьте четыре направления в массив смещений. Сложность любого варианта O(n·m).

Сами спросите условия: могут ли корабли касаться, бывают ли изогнутые, можно ли менять вход. От ответов зависит выбор решения.

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

Помечают клетку посещённой не сразу. В рекурсии это даёт бесконечное хождение между соседями, а в BFS с пометкой при извлечении одна клетка попадает в очередь несколько раз.

Портят входную матрицу, не спросив разрешения. На ревью это частый минус, особенно если поле дальше используется.

Выбирают рекурсию, не оценив глубину. На маленьких тестах всё работает, на большом поле программа падает.