5
let arr = [[1, 0, 1],
           [1, 0, 0],
           [1, 1, 1]
     ];

как мне получить количество островов, тут их 2 один вверху справа(одиночный) и один большой весь последний ряд и первая колонка. я обращался к элементам при помощи 2-ого цикла.

for (let i = 0; i < arr.length; i++) {
for (let x = 0; i < arr[i].length; x++) {
        if(...){
      }
   }
}

Так вот я никак не могу придумать условие помогите.

10
  • не понятно, что такое остров ? 8 дек 2017 в 16:00
  • @Даниил Судя по картинке - область из единиц, окруженная нулями (или границей карты)
    – Mike
    8 дек 2017 в 16:03
  • @Mike тоже так подумал, но так ли это 8 дек 2017 в 16:04
  • Вообще все не так тривиально, как просто два цикла. задача чем то напоминает ru.stackoverflow.com/q/727877/194569 и решается такими же способами ...
    – Mike
    8 дек 2017 в 16:04
  • Тут дело не просто в условии. Тут нужен алгоритм, и этот алгоритм не такой простой и тривиальный, как может показаться. 8 дек 2017 в 16:06

4 ответа 4

7

Тут нужно использовать алгоритм заливки изображения. Логика такая:

  1. Обход каждого пиксела.
  2. Если он == 1, то заливаем фигуру из единиц нулями, при этом инкрементим счётчик островов.
  3. В конце обхода получаем количество островов, и матрицу, заполненную нулями.

Алгоритм заливки там описан на C, но как ни странно - будет работать на JS, всего лишь заменив объявление функции, я капельку доработал, оставив только одну глобальную переменную screenBuffer:

//Recursive 4-way floodfill, crashes if recursion stack is full 
function floodFill4(x, y, newColor, oldColor = null) 
{ 
  if (!oldColor){
    oldColor = screenBuffer[x][y];
  }
  if(x >= 0 && x < screenBuffer.length && y >= 0 && y < screenBuffer[0].length && screenBuffer[x][y] == oldColor && screenBuffer[x][y] != newColor) 
  { 
    screenBuffer[x][y] = newColor; //set color before starting recursion

    floodFill4(x + 1, y,   newColor, oldColor);
    floodFill4(x - 1, y,   newColor, oldColor);
    floodFill4(x,   y + 1, newColor, oldColor);
    floodFill4(x,   y - 1, newColor, oldColor);
  }   
}
6
  • Я посоветую не использовать рекурсию. Для этой задачи лучше поиск в ширину а не в глубину.
    – pavel
    8 дек 2017 в 16:19
  • @pavel есть много решений для заливки, например трассировка линиями - описанная в том-же посте по ссылке. Этот просто самый короткий и очевидный. 8 дек 2017 в 16:21
  • @Дмитрий Полянин эм, логика решения задачи до конца описана (читай после слов Логика такая), больше добавить нечего.- разве что реализацию в строчки 4 кода, которую оставим автору вопроса. 8 дек 2017 в 16:42
  • @Гончаров Александр Да, я уже увидел, поэтому стёр комментарий. 8 дек 2017 в 18:10
  • не пойму как вы видите эти острова, вот что тут будит островом [[1, 0, 1], [0, 1, 0],[1, 0, 1]]
    – L11VADIS
    8 дек 2017 в 23:42
3

Эта задача называется поиск компонент связности графа. Решается в несколько этапов: - строим граф на основе матрицы. Каждую клетку с 1 делаем вершиной, соединяем её ребрами с непосредственными соседями (если они есть) - добавляем все вершины в массив - поиском в глубину или ширину начинаем обход с первой вершины. Удаляем вершины в которых побывали из массива, добавляем их в набор вершин острова. Если обход завершён, а массиве ещё есть вершины, создаём ещё один остров и начинаем обход заново с первой оставшейся вершины. Данный алгоритм имеет сложность по памяти и времени n, работает даже для вложенных бубликов

3

Набросал реализацию. В основе "построчная заливка". Чуть-чуть упростил т.к. сама заливка не нужна.

Добавил тестов. Если выполнить, то в консоли будет видно сколько их, какие прошли успешно, а какие нет.

Работает просто.

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

Нашли участок для которого слева и сверху вода? - Это начало нового острова. Нашли землю слева? - Это продолжение найденного ранее острова. Нашли выше кусок другого острова (другого, не текущего, это важно)? - Забываем про него навсегда: он является куском рассматриваемого.

В итоге число островов равно числу всех найденных новых минус число забытых в момент поглощения.

function calc(arr) {
    let rows = arr.length, cols = arr[0].length; // размеры матрицы

    let islands = 0; // порядковый номер последнего из найденных островов
    let eaten = []; // острова, примкнувшие к другим на поздних итерациях поиска

    // участок земели ..
    let left = 0, // .. слева от рассматриваемого и ..
        up = 0; // .. над рассматриваемым

    // является ли искомый остров в списке ранее примкнувших
    let isEaten = function (needle) {
        for (let i = 0; i < eaten.length; i++) {
            if (eaten[i] === needle) {
                return true;
            }
        }
        return false;
    };

    // перебираем матрицу с верхнего левого в нижний правый угол
    for (let row = 0; row < rows; row++) { // построчно сверху вниз
        for (let col = 0; col < cols; col++) { // а строки по столбцам слева направо
            if (!arr[row][col]) {
                continue; // пропускаем морские участки
            }
            left = col > 0
                ? arr[row][col - 1] // определяем участок земли слева
                : 0;
            up = row > 0
                ? arr[row - 1][col] // определяем участок земли сверху
                : 0;
            if (!left && !up) { // участок земли начинает остров, если слева и сверху нет земли
                islands++; // увеличиваем счётчик найденных островов
                arr[row][col] = islands; // запоминаем найденный участок
            } else if (left && !up) {
                arr[row][col] = left; // участок продолжает вправо ранее найденный остров
            } else if (!left && up) {
                arr[row][col] = up; // участок продолжает вниз ранее найденный остров
            } else if (left && up && up !== 1 && !isEaten(up)) {
                arr[row][col] = left; // участок продолжает вправо ранее найденный остров
                eaten.push(up); // а сверху к нему примыкает ранее не поглощённый остров - поглощаем его
            }
        }
    }

    return islands - eaten.length;
}

let tests = [
    [
        [
            [1, 0, 1],
            [1, 0, 1],
            [1, 1, 1],
        ],
        1
    ],
    [
        [
            [1, 1, 1],
            [1, 1, 0],
            [1, 0, 0],
        ],
        1
    ],
    [
        [
            [1, 0, 1],
            [1, 0, 0],
            [1, 1, 1],
        ],
        2
    ],
    [
        [
            [1, 0, 1],
            [1, 0, 0],
            [1, 0, 1],
        ],
        3
    ],
    [
        [
            [1, 1, 1],
            [1, 0, 1],
            [1, 1, 1],
        ],
        1
    ],
    [
        [
            [1, 0, 1],
            [0, 1, 0],
            [1, 0, 1],
        ],
        5
    ],
    [
        [
            [1, 0, 1, 1, 1],
            [1, 0, 0, 0, 1],
            [1, 1, 1, 0, 1],
            [0, 0, 0, 0, 1],
            [1, 1, 1, 1, 1],
        ],
        2
    ],
    [
        [
            [1, 1, 1, 1, 1],
            [1, 0, 0, 0, 1],
            [1, 0, 1, 0, 1],
            [1, 0, 0, 0, 1],
            [1, 1, 1, 1, 1],
        ],
        2
    ],
    [
        [
            [1, 0, 1],
            [1, 0, 1],
            [1, 0, 1],
        ],
        2
    ],
    [
        [
            [1, 0, 1, 0, 1, 0],
            [0, 0, 1, 1, 1, 0],
            [0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0],
        ],
        2
    ],
];

let result = [];
let fails = [];
console.log(`Tests: ${tests.length}`);
for (let i = 0; i < tests.length; i++) {
    let arr = tests[i][0];
    let expected = tests[i][1];
    let actual = calc(arr);
    if (expected !== actual) {
        result.push('F');
        fails.push(`#${i}: expected = ${expected}, actual = ${actual}`);
    } else {
        result.push('.');
    }
}
console.log(result.join(''));
console.log(fails.join(`\n`));

4
  • 1
    [[1, 0, 0, 0, 1], [1, 1, 0, 0, 1], [1, 1, 0, 0, 1], [1, 0, 0, 1, 1], [1, 0, 0, 1, 1]] 14 дек 2017 в 18:12
  • @ЕгорБанин ага, спс. поправил и добавил тест в набор.
    – Lexx918
    15 дек 2017 в 9:51
  • может я что-то не так понял, но код не универсален написанный Lexx918. Проверил вот на таком раскладе: [1, 0, 1, 0, 1, 0] [0, 0, 1, 1, 1, 0] [0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0] Результат не верный. Лично мне удалось простые варианты расстановки островов сделать Ifами elseами, а вот посерьезнее вариант увы провалился с крахом =(
    – Shter
    8 мар 2018 в 22:07
  • @Shter проверил, 2 острова, ошибки не вижу. Какой результат у вас? (добавил ваши данные в тело ответа, можно запустить скрипт и увидеть успешно пройденные тесты)
    – Lexx918
    23 мар 2018 в 13:08
0

Предложенный @Lexx918 код не верно считает количество островов. в массиве (считает что островов 3, а по факту 4)

[
  [1, 0, 0, 0, 1],
  [0, 0, 1, 0, 1],
  [0, 1, 0, 0, 0],
  [0, 1, 1, 1, 1],
  [0, 0, 0, 1, 1]
];

чуть доработал и упростил решение Lexx918

const map = [
  [1, 0, 0, 0, 1],
  [0, 0, 1, 0, 0],
  [0, 1, 0, 0, 1],
  [0, 1, 1, 1, 1],
  [0, 0, 0, 1, 1]
];

function findIslands(arr) {
  let rows = arr.length,
    cols = arr[0].length; // размеры матрицы

  let islands = 0;
  let eaten = []; // острова, примкнувшие к другим на поздних итерациях поиска

  let left = 0, // участок слева
    up = 0; // участок сверху

  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (!arr[row][col]) {
        continue; // море
      }
      left = col > 0 ?
        arr[row][col - 1] :
        0;

      up = row > 0 ?
        arr[row - 1][col] :
        0;
      if (!left && !up) { // участок земли начинает остров, если слева и сверху нет земли
        islands++;
        arr[row][col] = islands; // нумеруем остров
      } else if (left && up && left !== up) { //верхний остров поглощен
        arr[row][col] = left;
        eaten.push(up)
      } else if (left) {
        arr[row][col] = left; // участок продолжает вправо ранее найденный остров
      } else if (up) {
        arr[row][col] = up; // участок продолжает вниз ранее найденный остров
      }
    }
  }
  console.table(arr)
  return islands - eaten.length;
}

console.log('найдено островов ', findIslands(map))

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.