Answer

Ответ:

const getBattleshipsCount = (board) => {
  const rows = board.length;
  const cols = board[0].length;

  let result = 0;

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (board[i][j] == '.') continue;

      if (i > 0 && board[i - 1][j] == 'X') continue;

      if (j > 0 && board[i][j - 1] == 'X') continue;

      result++;
    }
  }

  return result;
};

Обьяснение:

Первый способ решения — это запустить поиск в глубину (DFS), пометить посещенные клетки корабля и посчитать общее количество кораблей. Поиск в глубину довольно дорогой метод по времени, также он использует рекурсию.

Чтобы избежать этого, мы можем оптимизировать наш алгоритм, используя тот, факт, что корабли могут распологаться только по горизонтали или только по вертикали. Т.е. нам нужно посчитать только первые клетки кораблей.

Если на очередном шаге мы встретили клетку корабля, мы проверяем предыдущую клетку по вертикали и по горизонатли, если там также находится клетка корабля, то мы пропускаем эту итерацию. Так как мы уже посчитали этот корабль раньше.

Если же на очередном шаге мы встретили клетку корабля и предыдушие клетки по горизонтали и вертикали не являются клетками корабля, то значит мы нашли 1ю клетку нового корабля. В этом случае увеличиваем наш результирующий счетчик.

Детали смотрите в коде.

Код для проверки:

const getBattleshipsCount = (board) => {
  const rows = board.length;
  const cols = board[0].length;

  let result = 0;

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (board[i][j] == '.') continue;

      // мы пропускаем следующие клетки корабля 'X',
      // т.к. уже посчитали корабль используя самую левую клетку по строке (начало корабля)
      if (i > 0 && board[i - 1][j] == 'X') continue;

      // мы пропускаем следующие клетки корабля 'X',
      // т.к. уже посчитали корабль используя самую верхнюю клетку по столбцу (начало корабля)
      if (j > 0 && board[i][j - 1] == 'X') continue;

      // иначе мы встретили начало нового корабля
      result++;
    }
  }

  return result;
};

const board = [
  ['X', '.', '.', 'X'],
  ['.', '.', '.', 'X'],
  ['.', '.', '.', 'X'],
];

console.log(getBattleshipsCount(board));