Распознание квадрата в двумерной матрице

#javascript #алгоритм

Сделал вот такой грид.



Просто матрица 8x8 из чисел (0, 1, 2, 3), на основе которой и заполняется канва. 

map =   [
        [0,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,0,0],
        [0,0,1,1,0,0,0,0],
        [0,0,1,1,0,0,0,0],
        [0,0,0,0,2,0,2,0],
        [0,0,0,0,0,3,0,1],
        [0,0,0,0,0,0,0,0],
        [0,0,0,0,0,0,0,0]
        ];


Цвет меняется кликом над белым квадратом. Один клик — одна смена цвета по возрастающей:
0(#000) -> 1(#f00) -> 2(#0f0) -> 3(#00f) -> 0 ...

Как определить, что после четырёх случаев изменения цвета пользователем, в матрице
появился квадрат 2х2 в любом месте грида? Например, как на скрине:



Очевидно, что после четырёх кликов квадрат можно собрать только из красных квадратов.
    

Ответы

Ответ 1

Самый простой алгоритм выделения квадрата 2х2 в заданной матрице может быть таким:


Начните обход матрицы с левого верхнего элемента и проверяйте построчно (это важно!),
двигаясь слева на право. При достижении правого края строки, переходите на самый левый
элемент следующей строки.
Если вы нашли элемент, значение которого равно единице, вы нашли левый верхний угол
квадрата. Обозначим его координаты как (X, Y).
Проверьте элементы с координатами (X+1, Y+1), (X, Y+1), (X+1, Y). Если все они равны
единице, то вы нашли квадрат. В противном случае, ваша матрица не содержит квадрата.
Если при достижении последнего элемента матрицы (W, H) вы так и не нашли ни одного
элемента со значением равным единице, то ваша матрица не содержит единичных (красных)
ячеек. Как следствие, она просто не может содержать в себе квадрата 2x2 из единиц.


Замечение: При проверке соседних элементов матрицы, координаты X+1 и Y+1 могут выходить
за границы исходной матрицы. Проверять значения таких элементов не имеет смысла.

UPD: При желании, алгоритм можно оптимизировать, например так:


При первоначальном обходе матрицы проверять не каждый элемент строки а через один.
Это поможет снизить количество проверок на W / 2.
Более того, можно проверять не каждую строку, а только через одну. Это позволит снизить
количество проверок на H / 2.
Наложение условий 1 и 2 требует проверки найденного единичного элемента не только
как левого верхнего, но и как любого углового. Если каждую из проверок начинать с противоположенного
угла квадрата, то это увеличит количество проверок на 3 в худшем случае.


Оптимизированная версия алгоритма в худшем случае потребует выполнения H * W / 4
+ 6 проверок. Для матрицы 8х8 в худшем случае это всего 22 итерации.


Ответ 2

В общем случае после каждого клика на точке необходимо проверить от 3 до 8 соседних
точек (в зависимости от расположения исходной).

Алгоритм примерно такой (для jscript уже сами подгоните)

if ((map [x,y-1] + map[x-1,y-1] + map[x-1,y] == 3)
|| (map [x-1,y] + map[x-1,y+1] + map[x,y+1] == 3)
|| (map [x,y+1] + map[x+1,y+1] + map[x+1,y] == 3)
|| (map [x+1,y] + map[x+1,y-1] + map[x,y-1] == 3))


где x и y, координаты точки, на которой произошел клик.

Т.е. в вашем случае при клике на точку, указанную как А, проверяются точки, указанные
как В.

map =   [
                [0,0,0,0,0,0,0,0],
                [0,B,B,B,0,0,0,0],
                [0,B,А,B,0,0,0,0],
                [0,B,B,B,0,0,0,0],
                [0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0]
                ];


Ответ 3

По клику проверяем изменившуюся ячейку, т.к. она могла создать квадрат с соседями.

Сначала проверяем четыре диагональные от неё ячейки, и, если нашлись не пустые, то
дополнительно проверяем смежные. Запустив сниппет, на цифрах можно кликать:



var map = [
    [0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0],
    [0,0,1,1,0,0,0,0],
    [0,0,1,0,0,0,0,0],
    [0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0]
  ], 
  $out = $('#out'),
  $2x2 = $('#2x2'),
  colors = ['r','g','b']
;

function makeMatrix(row, y){ return '[' + row.map( makeCell.bind(null,y)).join(',')
+ ']';}
function makeCell(y, cell, x) { return '' + cell + '';}
$out.html( '[
' + map.map( makeMatrix).join(',
') + '
]');

$('.cell').on('click', function(){
  var $el = $(this).removeClass().addClass('cell')
     ,x = $el.data('x')
     ,y = $el.data('y')
  ;
  $el.text( map[y][x] = (map[y][x]+1)%4);
  if(map[y][x]>0) $el.addClass( colors[map[y][x]-1]);
  $2x2.text('');
  [-1,1].map( function(i){
    var xx = x + i;
    if(xx < 0  ||  xx > 7) return;
    [-1,1].map( function(j) {
      var yy = y + j;
      if(yy < 0  ||  yy > 7) return;
      if( map[yy][xx] == 0) return;
      if( map[yy][x] == 0  ||  map[y][xx] == 0) return;
      // found 2x2
      $2x2.text( "Found: " + x+',' +y +' : ' +xx+',' +yy);
    });
  });
});
#out {font-family:Courier New,monospace;font-size:12px}
.cell {background-color: #EEE; cursor:pointer}
.r {background-color: #F99}
.g {background-color: #3F3}
.b {background-color: #99F}