Как написать счетчик островов?

269

10 декабря 2017, 13:20

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(...){
      }
   }
}

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

Answer 1

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

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

Алгоритм заливки там описан на 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);
  }   
}