Идея
Сначала преобразуйте (а вы сделали) свою матрицу в матрицу 0/1,
с 0 для не простых чисел и 1 для простых чисел.
Теперь у вас есть "поверхность" 1 с. Сколько квадратов вы можете поставить на этой поверхности?
Подумайте об этом: если у вас есть 3*3 квадрат 1 с, начинающийся с (0,0), то вы уже
Знайте, что квадраты (1,0)-(2,1), (0,1)-(1,2) и (1,1)-(2,2) состоят из 1 с, поэтому вам не нужно проверять эти квадраты снова.
Следовательно, вы будете искать квадраты 1 с, начиная с (1,0), (0,1) или (1,1), , только если они больше 2*2.
Представьте, что самый большой квадрат, начинающийся с (1,0), имеет размер 3*3, а два других - 2*2.
Вы можете игнорировать последнее (они не добавляют ничего нового), но вы должны добавить новый квадрат 3*3 и удалить перекрывающуюся поверхность с предыдущим.
Это можно обобщить следующим образом:
- хранить самый большой размер квадрата, начиная с
(0,0), в матрице M
- let
N = количество квадратов в квадрате размером M[0,0]
- для каждого
(r,c), слева направо и сверху вниз:
- получить от
M наибольшего размера квадрата, начиная с (r-1,c), (r,c-1) или (r-1,c-1), скажем, K
- вычисляет наибольший размер квадрата, начиная с
(r,c) (начиная с K-1)
- если
M[r,c] = K-1, ничего не делать
- , если
M[r,c]> K-1, обновить N: N + = количество квадратов в квадрате размером M[r,c] - количество
квадраты в квадрате размером K-1
Хитрость в том, что «вычисление наибольшего размера квадрата, начинающегося с (r,c) (начиная с K-1)» избавит от многочисленных сравнений.
Псевдокод (как Python)
Во-первых, обратите внимание, что квадрат размером k содержит k^2 квадратов размером 1, (k-1)^2 квадратов
размер 2, ..., 1 квадрат размера k. Это хорошо известная сумма (я взял результат из Википедии!):
subsquares_count(k) = 1/6*k + 1/2*k^2 + 1/3*k^3
Рассчитать размер самого большого квадрата из 1 s, начиная с (r, c), несложно. Я добавляю начало с K:
def largest_square_size(m, r, c, K):
k = K
while k<n:
# check the border
for l in 0..k:
if m[r+k, c+l] == 0 or m[r+l, c+k] == 0: # consider the left and bottom borders
break while
if m[r+k, c+k] == 0 # don't forget the corner
break while
k += 1
return k
Теперь эскиз основного цикла:
for r in 0..n:
for c in 0..n:
K = max(M[r-1,c-1], M[r-1,c], M[r,c-1]) - 1 # add boundary check, K = 0 if r,c = 0,0
M[r,c] = largest_square_size(m, r, c, K)
if M[r,c] > K:
N += subsquares_count(M[0,0]) - subsquares_count(K)
ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Я не проверял это, и, возможно, есть крайние случаи, но я думаю, что это правильно.
Это явно неоптимальный вариант, поскольку некоторые позиции можно проверять более одного раза, но они должны работать хорошо.