Алгоритм - Grid Map находит количество подблоков с определенным свойством

Question

У меня есть сетка NxN. Каждая ячейка может иметь значение "0" или "1". Я пытаюсь найти точное количество отдельных подблоков прямоугольника карты, которые включают определенное число '1', и это число может быть между 1 и 6. Я думал о поиске каждого возможного прямоугольника, но это очень медленно для карты размером 500x500 и решение должно быть ~ 1 сек для обычного настольного компьютера. Может кто-нибудь сказать мне соответствующую проблему, чтобы я мог искать работающий алгоритм или лучше может кто-то предложить мне рабочий алгоритм для этой проблемы? Спасибо всем заранее!

Answer 1

Я предполагаю, что ваш поиск всех прямоугольников идет медленно, потому что вы на самом деле рассчитываете на каждый возможный прямоугольник. Решением этой проблемы является не подсчет всех прямоугольников, а создание второго массива NxN, содержащего счетчик для прямоугольника (0,0..x,y), для вызова этого OriginCount. Затем, чтобы рассчитать количество для любого данного прямоугольника, вам не нужно будет проходить через прямоугольник и считать. Вы можете просто использовать

Count(a,b..c,d) = OriginCount(c,d) + OriginCount(a-1,b-1) -
                  OriginCount(a-1,d) - OriginCount(c,b-1)

Это превращает проблему подсчета единиц в любом данном прямоугольнике из задачи N ^{2 в} проблему с дискретным или постоянным временем, и ваш код становится в тысячи раз быстрее (для вашего случая 500x500)

Напоминаем, что для настройки массива OriginCount вы можете использовать ту же концепцию, а не просто подсчитывать единицы для каждого прямоугольника, от 0,0 до x,y. Скорее используйте формулу

OriginCount(x,y) = OriginCount(x-1,y) + OriginCount(x,y-1) - OriginCount(x-1,y-1) +
                   GridMap(x,y) == 1 ? 1 : 0;

Имейте в виду, вы должны учитывать крайние случаи - где х =0 или у =0.