У меня есть карта сетки NxN. Каждая ячейка может иметь значение «0» или «1». Я пытаюсь найти точное количество отдельных прямоугольных подблоков карты, которые включают определенное число «1», и это число может быть от 1 до 6. Я думал о поиске каждого возможного прямоугольника, но это очень медленно для карты размером 500х500 и решение должно быть ~1 сек для обычного стационарного компа. Может ли кто-нибудь рассказать мне о соответствующей проблеме, чтобы я мог найти рабочий алгоритм, или лучше кто-нибудь может предложить мне рабочий алгоритм для этой проблемы? Спасибо всем заранее!
Алгоритм - Карта сетки находит количество подблоков с определенным свойством
Ответы (1)
person
schedule
Но чтобы найти все прямоугольники с определенным количеством, алгоритм все равно должен получить
Count для всех возможных прямоугольников, что составляет N ^ 2, я думаю, что решение OP - N ^ 3, а ваше решение - N ^ 2.
- person Some Guy; 09.11.2016
@SomeGuy - я имел в виду проблему подсчета для данного прямоугольника. Я думаю, что исходная проблема ОП будет меняться от N ^ 3 до N ^ 2 (log N). Но прирост все равно будет в 100 раз быстрее. Я отредактировал, чтобы уточнить.
- person ; 09.11.2016
@SomeGuy - на самом деле, я думаю, что ошибся даже с первоначальной оценкой порядка величины. Счет для прямоугольника идет от N ^ 2 к алгоритму с постоянным временем, поэтому выигрыш в скорости должен быть даже больше, чем я сказал.
- person ; 09.11.2016
