Расположить форму в 2D массив целых чисел

Question

на фиксированной карте размера целых чисел

1,1,1,0,0,0,0,0,0,0,0,0,0 
0,1,1,0,0,1,0,0,0,0,0,0,0 
0,0,1,0,1,2,1,0,0,1,2,0,0 
0,0,0,0,0,0,0,0,0,0,0,0,0 

найти, где находится произвольная форма повёрнутый:

0,0,0,1,0 
1,0,1,1,1 

Выход: [2,1] (Верхний левый угол формы)

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

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

Другой подход состоит в том, чтобы суммировать строки и столбцы карты и формы, а затем находить возможные варианты решений, а затем проверять их, чтобы увидеть, работают ли они. Это поможет только тогда, когда карта будет малонаселенной.

Можете ли вы предложить лучший подход? Стремление уменьшить сложность Big O.

Answer 1

Одна из возможных оптимизаций заключается в использовании integral image.

Выполните следующие действия:

1) Найти наибольшее значение в вашей форме, а затем предварительно обработать карту зажимая все значения выше, чем максимум до макс.

2) Создайте интегральный массив изображений, в котором запись ii [y] [x] содержит сумму всех записей на карте [j] [i], где j < = y и i < = x, вычислено аналогичное к этому:

for(int y = 0; y <= rows; y++) 
{ 
    int rowsum = 0; 
    for(int x = 0; x <= columns; x++) 
    { 
     rowsum += map[y][x]; 
     ii[y][x] = rowsum + (y > 0) ? ii[y-1][x] : 0; 
    } 
} 

Вы можете использовать интегральный массив изображения, чтобы быстро вычислить сумму всех записей в заданном прямоугольнике карты с помощью всего 4 поиска в массиве (верхние границы проверки индексов массивов опущенных):

int computeRectSum(int x, int y, int width, int height) 
{ 
    int sum = ii[y + (height - 1)][x + (width - 1)]; 
    if(x > 0) 
     sum -= ii[y + (height - 1)][x-1]; 
    if(y > 0) 
     sum -= ii[y-1][x + (width - 1)]; 
    if((x > 0) && (y > 0)) 
     sum += ii[y-1][x-1]; 
    return sum; 
} 

3) Суммировать все значения в вашем поиске форма.

4) Перейдите по карте и для каждого (x, y) вычислите сумму прямоугольника для (x, y, ширину формы, высоту фигуры). Если это меньше суммы формы, тогда на карте не может быть возможной формы с ее верхним левым углом в (x, y), чтобы вы могли пропустить ее. В противном случае проверьте.

Как и подсчет строк и столбцов, эта оптимизация будет работать лучше всего с разреженными массивами, но я считаю, что производительность должна быть немного лучше, потому что это более локализованный тест. Вы можете использовать оба из них сразу: если сумма для строки меньше суммы верхней строки для формы, тогда исключить эту целую строку.

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

Проверка формы, когда тест в (4) проходит:

Для больших форм можно (ширина-первых) рекурсивно подразделяют форму, тестирование субрегионов на каждом шагу: сначала протестировать весь прямоугольник формы с интегральным изображением (т. е.шаг 4), то, если это будет разделено на 4 субрегиона и протестировать их таким же образом, тогда проверьте суб-суб-регионы и т. д., пока вы не окажетесь в субэкспорте 1x1, в этом случае вы просто выполняете свою первоначальную проверку , Вы должны были бы вычислить интегральное изображение для формы и использовать этот алгоритм.