Вы можете решить это за N ^ 3.Для каждой ячейки (x, y) вам нужна функция, которая сообщает, есть ли пустой квадрат высоты = z, z от 0 до n и с (справа, снизу) = (x, y).
Теперь проблема в том, как создать эту функцию.
И вы можете сделать это с частичными суммами.для каждой ячейки (x, y) сохраните DP [x] [y] = nr пешек в прямоугольнике (0,0), (x, y).Тогда вы можете ответить на функцию в O (1).
Полезные ссылки:
https://en.wikipedia.org/wiki/Summed-area_table
Edit # 1 (n ^ 2logn):
Я думаюВы можете увеличить производительность (N ^ 2 * log (N)), выполнив бинарный поиск по высоте квадрата в функции, описанной выше.Это работает, потому что если для z = 10 (означает, что вы можете поместить квадрат высотой 10 с (снизу, справа) в (x, y)), то очевидно, что вы также можете поместить квадрат с z = 9,8,7 ...1.
Редактировать # 2 (n ^ 2):
Да, вы были правы, вы можете сделать это за n ^ 2 :).Подумайте о функции выше, вопрос в том, какая наибольшая z (высота) для текущего (x, y), если я знаю ответ для (x-1, y), (x, y-1) и (x-1, у-1)?Итак, вот идея: самый большой z для текущей позиции = минимум z из (x-1, y), (x, y-1), (x-1, y-1) + 1;
int n,m,dp[100][100],rs;
char a[100][100];
int main() {
std::cin >> n >> m;
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
std::cin >> a[i][j];
}
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
if (a[i][j] == 'x') continue;
rs += dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1;
}
}
std::cout << rs << std::endl;
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) std::cout << dp[i][j] << ' ';
std::cout << endl;
}
return 0;
}
И пример вывода:
4 4
....
....
.xx.
....
17
1 1 1 1
1 2 2 2
1 0 0 1
1 1 1 1