algorithm - 在棋盘中找到所有可能的方 block ，不包括选定的单元格

Question

我在寻找棋盘问题中的所有方 block 方面略有不同。

我知道我们可以从大小为 8x8 的棋盘中找到所有可能的方 block 前8个数的平方和1^2 + 2^2 + 3^2 + 4^2 ... 8^2

但是如果有一些单元格被棋子占据，我们需要排除所有包含这些棋子的方格。

例如考虑下面的 4x4 矩阵

. . . .

. . . .

. x x .

. . . .

总平方 = 30 - {1(4x4) + 4(3x3) + 6(2x2) + 2(1x1)} = 30 - 13 = 17

我想用 DP 解决它，但无法准确确定如何排除禁止方 block 。

提前致谢!

Answer 1

你可以在 N^3 中解决它。对于每个单元格 (x,y)，您需要一个函数来判断是否存在高度 = z、z 从 0 到 n 的空方 block ，并且 (right, bottom) = (x,y)。

现在的问题是如何创建这个函数。

你可以用部分和来做到这一点。对于每个单元格 (x,y)，保存矩形 (0,0)、(x,y) 中棋子的 DP[x][y] = nr。然后你就可以在 O(1) 中回答这个函数。

有用的链接:

https://en.wikipedia.org/wiki/Summed-area_table

编辑 #1 (n^2logn):
我认为您可以通过对上面讨论的函数中的正方形高度进行二分搜索来提高性能 (N^2*log(N))。它之所以有效，是因为如果对于 z=10(意味着你可以在(x，y)中放置一个高度为 10 的正方形(底部，右))那么很明显你也可以放置一个 z=9,8,7 的正方形 .. .1.

编辑 #2 (n^2):
是的，你是对的，你可以在 n^2 中完成:)。想想上面的函数，问题是:如果我知道 (x-1,y),(x,y-1) 和 (x-) 的响应，当前 (x,y) 的最大 z(高度)是多少？ 1,y-1)?所以这里的想法是:当前位置的最大 z = 来自 (x-1,y),(x,y-1),(x-1,y-1) + 1 的 z 的最小值；

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