0

Привет!

Есть двумерный массив типа такого:

var matrix = new Array(
[1, 0, 0, 1, 1, 1, 0, 1, 0, 0],
[1, 0, 0, 1, 1, 0, 0, 1, 1, 0],
[0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
[1, 0, 0, 1, 1, 1, 0, 1, 0, 0]
);

Требуется искать определенные "фигуры" внутри массива, например, найти

[0, 0],
[0, 0]

или

[0],
[0],
[0, 0, 0]

Подскажите, возможно, есть какие-либо готовые алгоритмы для такого поиска?

1
  • @abirakir, Если вам дан исчерпывающий ответ, отметьте его как верный (нажмите на галку рядом с выбранным ответом). 13 мар 2015 в 14:17

2 ответа 2

1

Решал похожую задачу - поиск контуров при подсчете очков в игре Го (там, правда, было трехцветное решение - черный, белый, пусто).

Если на пальцах, в вашем случае превращаем исходный массив A (1 - пусто, 0 - есть фигура):

1001110100
1001100110
0111010001
1001110100

в другой массив B (пробел - отсутствие фигуры, одинаковые символы - части одной фигуры):

 11   2 33
 11  22  3
4   5 222 
 66   2 22

Алгоритм:

  • B заполняется пустыми значениями
  • Поочередно обходим все ячейки A
    • если ячейка пуста - нет фигуры, пропускаем
    • если ячейка заполнена - есть фигура, смотрим соседние ячейки в B
      • если соседние - только пустые, то ячейка - часть новой фигуры
      • если соседние содержат символ одной фигуры, то ячейка - часть этой фигуры.
      • если соседние содержат символы от разных фигур, то ячейка - это звено соединяющее разные фигуры, и эти фигуры нужно объединить в одну
    • в B помечаем, что текущая ячейка принадлежит фигуре, найденной в предыдущем пункте

Код

function getShapes(A){
   var B=[],empty=1,newCharCode=49;
   function b(i,j){return B[i]&&B[i][j];}
   function concatFigure(i,j,to){
      var bij=b(i,j);
      if(!bij||bij==to)return;
      B[i][j]=to;
      concatFigure(i-1,j,to); concatFigure(i,j-1,to);
      concatFigure(i+1,j,to); concatFigure(i,j+1,to);
   }
   A.forEach(function(row,r){
      B.push([]);
      row.forEach(function(el,c){
         if(el==empty) return B[r][c]=undefined; //нет фигуры
         var near=[b(r-1,c), b(r+1,c), b(r,c-1), b(r,c+1)],
            figures=near.filter(function(e,i,a){return e && a.indexOf(e)==i;}),
            char=figures[0] || String.fromCharCode(newCharCode++);
         if(figures.length<2)//если рядом 1 или 0 фигур - все просто
            return B[r][c]=char;
         B[r][c]=figures[1];//а если их много - переделаем в одну
         concatFigure(r,c,char); 
      });
   });
   return B;
}
//Вывод
var A=[[1,0,0,1,1,1,0,1,0,0],[1,0,0,1,1,0,0,1,1,0], [0,1,1,1,0,1,0,0,0,1], [1,0,0,1,1,1,0,1,0,0]],
    B=getShapes(A);
document.write("Исходный массив<pre>"+A.map(r=>r.join('')).join('\n')+"</pre>");
document.write("Фигуры<pre>"+B.map(r=>r.map(e=>e?e:' ').join('')).join('\n')+"</pre>");

1
  • Вы забыли указать, что код в ECMA6 стандарте
    – korytoff
    1 фев 2016 в 20:51
0

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

Разумеется, делать так имеет смысл, если в языке есть эффективные средства поиска подпоследовательностей. Иначе - да, четыре вложенных цикла. Хотя лучше все же внутренние два цикла выделить в отдельную функцию. Но это уже детали реализации.

Если речь идет о черно-белой картинке не шире 64 пикселей в ширину, то можно попробовать представить ее как набор чисел, в которых установлены соответствующие биты. Не уверен, что это даст что-то в плане производительности. Да и читаемость пострадает. Но вдруг...

И еще. Подмассивы, которые надо искать, лучше пусть будут как можно более однотипными, это упростит код. Я имею в виду, что если самая большая из них 3х3, то пусть все будут 3х3. При этом надо одно из значений отвести под "прозрачный цвет". Например, квадрат

[ 0, 0 ]
[ 0, 0 ]

Можно искать как

[ 0, 0, -1 ]
[ 0, 0, -1 ]
[ -1, -1, -1 ]

Где -1 означает, что соответствующий элемент "большого" массива может быть любым.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

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