问题分析

本问题的核心是从一个 的二值矩阵（. 与 *）中识别并统计所有由 . 组成的连通分量，并判断这些连通分量在几何形状上是否为完美的实心矩形。

关键约束：

  1. 连通性定义：题目指出图案之间“互不连通”。在方格网剪裁的语境下，这通常意味着两个 . 区域若共享一条边，则它们属于同一个图案（四连通性）。
  2. 矩形判定标准：一个连通分量是矩形的充分必要条件是：该分量包含的所有单元格恰好填满了由其坐标极值（上下左右边界）所定义的矩形区域，且该区域内不存在 *。

算法：几何闭包验证法（Geometric Closure Verification）

为了高效解决此问题，我们采用基于广度优先搜索（BFS）或深度优先搜索（DFS）的连通分量提取算法。通过计算每个连通分量的“几何特征”来判定其形状。

1. 核心算法

  • Flood Fill（种子填充）：这是处理格点图连通性问题的标准范式。
  • 形状判定逻辑：在遍历一个特定的连通分量 时，实时维护该分量的包围盒（Bounding Box）：
    • ：所有属于 的格点的行索引最小值与最大值。
    • ：所有属于 的格点的列索引最小值与最大值。
    • ：属于该连通分量的格点总数。

2. 矩形判定

对于一个连通分量 ，它是矩形的当且仅当： 证明：矩形区域内的格点总数等于其宽与高的乘积。若连通分量为矩形，则其内部必须包含该范围内的所有格点；若 小于该乘积，说明该区域内部存在“孔洞”（即 *）或者边缘不整齐（非矩形）。

复杂度分析

维度 复杂度分析 说明
时间复杂度 每个网格单元仅被访问两次：一次在全局扫描中，一次在 Flood Fill 中。
空间复杂度 需要一个等大规模的 visited 数组记录状态；递归 DFS 可能导致栈溢出，建议用队列实现 BFS。

对比备选方案：

  • 二维前缀和/扫描线：虽然可以判断矩形，但对于不规则区域的边界识别较复杂，不如 Flood Fill 直观且易于实现。
  • 局部模式匹配（如 检查）：虽然可以发现某些非矩形结构，但无法处理复杂的连通性逻辑。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static constexpr array<int, 4> dx{0, 0, -1, 1};
static constexpr array<int, 4> dy{-1, 1, 0, 0};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<bool>> visited(n, vector<bool>(m, false));
    vector<string> grid(n);

    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }

    auto bfs = [&](int i, int j) -> bool {
        int r_min = i;
        int r_max = i;
        int c_min = j;
        int c_max = j;
        int S_cnt = 0;

        queue<pair<int, int>> Q;
        Q.push({i, j});
        visited[i][j] = true;

        while (!Q.empty()) {
            auto [r, c] = Q.front();
            Q.pop();
            S_cnt++;

            r_min = min(r_min, r);
            r_max = max(r_max, r);
            c_min = min(c_min, c);
            c_max = max(c_max, c);

            for (int k = 0; k < 4; k++) {
                int nr = r + dx[k];
                int nc = c + dy[k];

                if (nr < 0 || nr >= n || nc < 0 || nc >= m || grid[nr][nc] == '*' ||
                        visited[nr][nc])
                    continue;

                visited[nr][nc] = true;
                Q.push({nr, nc});
            }
        }

        int area = (r_max - r_min + 1) * (c_max - c_min + 1);
        return S_cnt == area;
    };

    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '.' && !visited[i][j]) {
                if (bfs(i, j))
                    ans++;
            }
        }
    }

    cout << ans << endl;
}