Это популярный вопрос о кодировании, который задают многие компании.

Описание:

Учитывая двумерную сетку с 1 (суша) и 0 (вода), подсчитайте количество островов. Остров окружен водой и образован путем соединения соседних земель по горизонтали или вертикали. Вы можете предположить, что все четыре края сетки окружены водой.

Пример:

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

На первый взгляд, мы можем просто перебирать матрицу, пока не встретим остров, и использовать DFS на этом острове, чтобы найти его соседей.

Давайте посмотрим, как это выглядит:

  1. Установите переменную (total), в которой будет храниться количество островов, с которыми мы столкнулись изначально.
  2. Повторите матрицу, и как только мы встретим остров, мы обновим нашу общую переменную и применим нашу вспомогательную функцию DFS.
  3. Верните нашу итоговую переменную.

Как выглядит наша функция DFS?

  1. Поскольку наша функция DFS будет использоваться рекурсивно, нам сначала нужно проверить, что мы все еще находимся в границах сетки и что текущая точка, в которой мы находимся, все еще является частью острова.
  2. Затем нам нужно будет отметить каждый остров, который мы посетили, чтобы предотвратить дублирование подсчета.
  3. Затем мы можем рекурсивно применить нашу функцию DFS к соседним островам, которые находятся выше, ниже, слева и справа от нашего текущего положения.

Вот реализация Javascript:

const visited = (i, j, grid) => {
  let height = grid.length;
  let width = grid[0].length;
  if (i < 0 || i === height || j < 0 || j === width || grid[i][j]
  !== '1') return;
  grid[i][j] = 'X';
  visited(i + 1, j, grid);
  visited(i — 1, j, grid);
  visited(i, j + 1, grid);
  visited(i, j — 1, grid);
};
const numIslands = (grid) => {
  let total = 0;
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      if (grid[i][j] === “1”) {
        total += 1;
        visited(i, j, grid);
      }
    }
  }
  return total;
};