C++程序查找所有填充为0的矩形

在C++中，有许多方法可以查找所有填充为0的矩形。本文将介绍两种实现方式：深度优先搜索（DFS）和利用2D前缀和数组进行计算。

利用DFS寻找填充为0的矩形

使用DFS方法，我们可以深入到二维数组中，查找所有以0填充的矩形。具体实现如下。

#include<iostream>
#include<cstring>
using namespace std;

const int MAXN = 1005;
int graph[MAXN][MAXN];
bool visited[MAXN][MAXN];
int rect[MAXN][MAXN];
int x, y;

void dfs(int i, int j, int color) {
    if (i < 1 || j < 1 || i > x || j > y)
        return;
    if (visited[i][j] || graph[i][j] != color)
        return;
    visited[i][j] = true;
    rect[i][j] = rect[i - 1][j] + rect[i][j - 1] - rect[i - 1][j - 1] + 1;
    dfs(i + 1, j, color);
    dfs(i - 1, j, color);
    dfs(i, j + 1, color);
    dfs(i, j - 1, color);
}

int main() {
    cin >> x >> y;
    memset(visited, 0, sizeof(visited));
    memset(rect, 0, sizeof(rect));
    for (int i = 1; i <= x; i++) {
        for (int j = 1; j <= y; j++) {
            cin >> graph[i][j];
        }
    }
    int cnt = 0;
    for (int i = 1; i <= x; i++) {
        for (int j = 1; j <= y; j++) {
            if (!visited[i][j] && graph[i][j] == 0) {
                dfs(i, j, 0);
                cnt++;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

以上代码的主要思路是扫描整个二维数组。如果发现某个可行的格子（值为0）没有被访问，则将其作为新的矩形起点进入DFS搜索。此时，搜索将会将整个连续的矩形区域进行搜索，并标记访问过的矩形区域。

在DFS中，我们还用了范围查询的技巧和矩形加法器的关系（rect[i][j] = rect[i-1][j] + rect[i][j-1] – rect[i-1][j-1] + 1）。范围查询指的是查询以指定点为左上角顶点的连续矩形区域值的操作；矩形加法器则是将某个新的节点加入矩形区域时，更新矩阵区域值的操作。这些技巧在代码中都有做出示例。

利用2D前缀和数组进行计算

使用2D前缀和数组，我们可以更高效地查找填充为0的矩形。具体实现如下。

#include<iostream>
#include<cstring>
using namespace std;

const int MAXN = 1005;
int n, m;
int graph[MAXN][MAXN];
int dp[MAXN][MAXN];

int main() {
    cin >> n >> m;
    memset(dp, 0, sizeof(dp));
    memset(graph, 0, sizeof(graph));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> graph[i][j];
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + (!graph[i][j]);
        }
    }
    int ans = 0;
    for (int r1 = 1; r1 <= n; r1++) {
        for (int c1 = 1; c1= 1; c1 <= m; c1++) {
            for (int r2 = r1; r2 <= n; r2++) {
                for (int c2 = c1; c2 <= m; c2++) {
                    int cnt = dp[r2][c2] + dp[r1 - 1][c1 - 1] - dp[r2][c1 - 1] - dp[r1 - 1][c2];
                    if (cnt == (r2 - r1 + 1) * (c2 - c1 + 1)) {
                        ans++;
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

以上代码的主要思路是，我们需要预先建立一个加权前缀和数组。通过依次查找不同区域的前缀和，我们可以从矩阵中查找所有填充为0的矩形。在这里，2D前缀和数组就解决了搜索不连续矩阵的问题，更加灵活和高效。

代码中的核心计算特别简洁，通过以下代码可以实现：int cnt = dp[r2][c2] + dp[r1 – 1][c1 – 1] – dp[r2][c1 – 1] – dp[r1 – 1][c2];。此时，我们可以借助前缀和，实现一次O(1)即可计算cnt，不同块的计算就相当于矩形区域的加法运算。最终统计所有符合条件的矩形，得到我们所需的结果。