题目理解

我们有一个 $N \times N$ 的网格，每个格子是 # 或 .。 要数出所有由 # 组成的底边在下方、顶点在上方的正三角形的个数。 三角形的高度 $h$ 表示行数，第 $i$ 行有 $2i-1$ 个 #，且居中对齐。

算法思路

问题转化

如果以某个 # 作为三角形的最底部中心，那么它能形成的最大高度取决于它向上、向左上、右上的连续 # 数量。

关键结论

• 设 $g[i][j]$ 表示从 $(i,j)$ 向上连续 # 的个数（包括自己）。
• 设 $f[i][j]$ 表示以 $(i,j)$ 为底部中心时，向左上方向能延伸的最大长度。
• 设 $F[i][j]$ 表示以 $(i,j)$ 为底部中心时，实际能形成的最大三角形高度。

构造策略

1. 向上连续 # 计数：

   $$g[i][j] = \begin{cases} g[i-1][j] + 1, & \text{if } a[i][j] = \text{`\#'} \\ 0, & \text{otherwise} \end{cases} $$

2. 向左上连续 # 计数：

   $$f[i][j] = \min(g[i][j],\ f[i][j-1] + 1)$$

3. 实际三角形高度：

   $$F[i][j] = \min(g[i][j],\ F[i][j+1] + 1)$$

4. 计数方法： 对于每个 # 格子 $(i,j)$，它能形成的三角形个数为 $\min(f[i][j], F[i][j])$。

代码步骤解析

1. 输入与初始化

cin >> N;
n = N + 1u;

2. 计算向上连续 # 和左上延伸

for (unsigned I(0u), i(1u); i != n; ++ I, ++ i) {
    for (unsigned J(0u), j(1u); j != n; ++ J, ++ j) {
        cin >> x;
        if (a[i][j] = x == '#')
            f[i][j] = min(g[i][j] = g[I][j] + 1u, f[i][J] + 1u);
    }

• 计算 $g[i][j]$ 和 $f[i][j]$

3. 计算实际三角形高度并累加答案

    for (unsigned j(N), jj(n); j; -- j, -- jj)
        if (a[i][j])
            ans += min(f[i][j], F[i][j] = min(g[i][j], F[i][jj] + 1u));
}

• 从右到左计算 $F[i][j]$
• 累加每个 # 格子的贡献

4. 输出结果

cout << ans;

复杂度分析

• 时间复杂度：$O(N^2)$，每个格子常数次操作。
• 空间复杂度：$O(N^2)$，存储 $g, f, F$ 数组。

示例验证

样例

输入：

5
.....
.###.
.###.
#####
.....

输出：

16

• 高度 1 的三角形：11 个
• 高度 2 的三角形：4 个
• 高度 3 的三角形：1 个 总和 = 16

算法标签

• 动态规划
• 预处理优化
• 网格遍历

总结

本题通过动态规划预处理三个方向的连续 # 长度，从而在 $O(N^2)$ 时间内统计所有可能的三角形个数。关键思路是将三角形计数转化为对每个可能底部中心的高度计算，通过三个方向的约束确定最大可能高度。