Поле морского боя задано матрицей из 0 и 1: 1 — клетка корабля, 0 — вода.
Корабль — прямая полоска 1×k или k×1 (k ≥ 1), расположенная горизонтально
или вертикально. Корабли не касаются друг друга сторонами (касание углами
допустимо), то есть между любыми двумя кораблями по горизонтали и вертикали есть
хотя бы одна клетка воды. Посчитайте, сколько на поле кораблей.
// CountShips возвращает число кораблей на поле grid.
func CountShips(grid [][]int) int
Пример
1 1 1 0 1 0
0 0 0 0 0 0
0 0 1 0 1 0 → 5
0 0 0 0 1 0
1 1 1 0 1 0
0 0 0 0 1 0
Корабли: три клетки в верхнем ряду, одиночный справа сверху, одиночный в
центре, вертикальный из четырёх клеток в пятом столбце и три клетки в пятом ряду.
Ограничения
- Поле прямоугольное
M×N, 0 ≤ M, N, M·N ≤ 4·10⁶; вход гарантированно
корректен (только прямые корабли, не касающиеся сторонами).
- Поле менять нельзя.
- Ожидается один проход за O(M·N) и O(1) дополнительной памяти.
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.