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

Question

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

我知道我们可以从大小为 8x8 的棋盘中找到所有可能的方块前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来解决，但无法准确确定如何排除禁止方块。

提前致谢！

Answer 1

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

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

Find all the possible squares in a chessboard excluding selected cells

algorithm

dynamic-programming

combinatorics