CF518F 题解

观察到一条管道的拐点数量只有 \(3\) 种可能的取值：

• 没有拐点，即管道呈现一条直线。
• 有 \(1\) 个拐点。
• 有 \(2\) 个拐点。

分别对应了下面三种情况：

....#           ....#            .*..#
*****           ****.            .***.
..#..           ..#*.            ..#*.
#...#           #..*#            #..*#
.....           ...*.            ...*.

考虑对这三种情况分别计数，先预处理出来几个辅助数组 ( bool 类型 ) \(U[i][j], D[i][j], L[i][j], R[i][j]\)，\(U[i][j]\) 表示从 \((i, j)\) 到 \((1, j)\) 的路上是否无障碍物，即从 \((i, j)\) 一直往上走的路径上是否无障碍物。\(D[i][j], L[i][j], R[i][j]\) 同理，分别表示往下走 \((i, j) \to (n, j)\)、往左走 \((i, j) \to (i, 1)\)、往右走 \((i, j) \to (i, m)\) 的路上是否不存在障碍物。特别地，对于有障碍物的格子 \((i, j)\)，有 \(U[i][j] = D[i][j] = L[i][j] = R[i][j] = 0\)。

分类讨论拐点数量：

• 对于没有拐点的情况，答案是 \(\sum\limits_{i=2}^{n-1}R[i][0]+\sum\limits_{i=2}^{m-1}D[0][i]\)。
• 对于有 \(1\) 个拐点的情况，考虑枚举拐点的位置，接着枚举管道通往的方向，并根据对应的 \(U, D, L, R\) 数组计算贡献即可。这部分的答案为 \(\sum\limits_{i = 2}^{n - 1}\sum\limits_{j = 2}^{m - 1} (L[i][j] + R[i][j]) \times (D[i][j] + U[i][j])\)。
• 对于有 \(2\) 个拐点的情况，分成两种子情况：第一种是管道先竖着走再横着走再竖着走；第二种是先横着走再竖着走再横着走。可以发现两种情况类似，下面只讨论第一种情况：
  先枚举横着走的那一行，从左往右扫每一列，记当前行为 \(i\)，列为 \(j\)。记录两个值 \(toU, toD\)，分别表示 \(2 \sim (j - \textbf{2})\) 中有多少列能向上走，有多少列能向下走，且第 \(i\) 行内第 \(j\) 列与这些列之间没有障碍物。考虑贡献答案，先特殊考虑 \(j - 1\) 列的贡献 ( 因为 \(j\) 列和 \(j - 1\) 列不能同时往上或者同时往下 )，再考虑 \(2 \sim (j - 2)\) 列，显然这部分对答案贡献为 \((U[i][j] + D[i][j]) \times (toU + toD)\)。离开第 \(j\) 列时更新一下 \(toU\) 和 \(toD\) 即可。
  第二种情况类似处理出 \(toL\) 和 \(toR\) 即可。

至此本题解决，复杂度 \(O(nm)\)。下面是代码：

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

using i64 = long long;

signed main(void) {
    ios :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;
    vector <vector <char>> a(n, vector <char> (m));
    vector <vector <int>> u(n, vector <int> (m));
    auto d = u, l = u, r = u;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> a[i][j];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            u[i][j] = (!i ? 1 : u[i - 1][j]) && (a[i][j] == '.');
            l[i][j] = (!j ? 1 : l[i][j - 1]) && (a[i][j] == '.');
        }
    }
    for (int i = n - 1; i >= 0; --i) {
        for (int j = m - 1; j >= 0; --j) {
            d[i][j] = (i + 1 == n ? 1 : d[i + 1][j]) && (a[i][j] == '.');
            r[i][j] = (j + 1 == m ? 1 : r[i][j + 1]) && (a[i][j] == '.');
        }
    }

    i64 ans = 0;
    for (int i = 1; i + 1 < n; ++i)
        ans += r[i][0];
    for (int j = 1; j + 1 < m; ++j)
        ans += d[0][j];

    for (int i = 1; i + 1 < n; ++i)
        for (int j = 1; j + 1 < m; ++j)
            ans += (l[i][j] + r[i][j]) * (d[i][j] + u[i][j]);

    for (int j = 1; j + 1 < m; ++j) {
        int toL = 0, toR = 0;
        for (int i = 1; i + 1 < n; ++i) {
            if (l[i][j])
                ans += toL + toR + (i > 1 && r[i - 1][j]);
            if (r[i][j])
                ans += toL + toR + (i > 1 && l[i - 1][j]);
            if (i > 1) {
                toL += l[i - 1][j];
                toR += r[i - 1][j];
            }
            if (a[i][j] == '#') {
                toL = 0;
                toR = 0;
            }
        }
    }
    for (int i = 1; i + 1 < n; ++i) {
        int toU = 0, toD = 0;
        for (int j = 1; j + 1 < m; ++j) {
            if (u[i][j])
                ans += toU + toD + (j > 1 && d[i][j - 1]);
            if (d[i][j])
                ans += toU + toD + (j > 1 && u[i][j - 1]);
            if (j > 1) {
                toU += u[i][j - 1];
                toD += d[i][j - 1];
            }
            if (a[i][j] == '#') {
                toU = 0;
                toD = 0;
            }
        }
    }

    cout << ans << '\n';
}