Reachable Cells

xht · 2023-09-27 01:28:36 · 题解

Reachable Cells

题意

• 给定一个 n \times n 的网格，每个位置上要么是障碍，要么写有一个 [1,9] 的数。
• 我们称位置 x 可以到达位置 y 当且仅当：
  • 存在一条从 x 到 y 的路径，满足只经过不是障碍的格子，同时每次只向下或者向右走到相邻的格子。
• 对于二元组 (x,y)，若 x 可以到达 y，则 (x,y) 合法且权值为 x,y 上写的数的乘积。
• 要求所有合法二元组的权值之和。

题解

考虑从大到小枚举位置 (i,j) 求出能到达的点的权值和 s_{i,j}。

如果 (i,j+1) 和 (i+1,j) 中至多一个不是障碍则很简单，否则直接加 s_{i+1,j} 和 s_{i,j+1} 会算重，要减掉两个点都可达的。

设 l_{i,j,k},r_{i,j,k} 表示 (i,j) 能到达的点在第 k 行列数的最小值和最大值，显然对于 (i,j+1) 和 (i+1,j) 都能到达的行 k 有 l_{i+1,j,k} \le l_{i,j+1,k}，r_{i+1,j,k} \le r_{i,j+1,k}。

注意到如果第 k 行有 (i,j+1) 和 (i+1,j) 都能到达的点，那么必然包括 (k,l_{i,j+1,k})，且 (i,j+1) 和 (i+1,j) 都能到达的点恰好为若干个 (k,l_{i,j+1,k}) 能到达的点的并集，使这些点集不交。

于是可以 \mathcal O(n^3) 计算，常数很小可以通过，注意滚动数组防止炸空间。

代码

const int N = 1.5e3 + 7;
int n, s[N][N], p[N][N], l[2][N][N], r[2][N][N];
char a[N][N];
ll ans;

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) rds(a[i], n);
    for (int i = n, o = 0; i; i--, o ^= 1)
        for (int j = n; j > 0; j--)
            if (a[i][j] != '#') {
                a[i][j] -= '0';
                s[i][j] = s[i][j+1] + s[i+1][j] + a[i][j];
                p[i][j] = max(max(p[i][j+1], p[i+1][j]), i);
                l[o][j][i] = j;
                for (int k = i + 1; k <= p[i+1][j]; k++)
                    l[o][j][k] = l[o^1][j][k];
                for (int k = max(p[i+1][j], i) + 1; k <= p[i][j+1]; k++)
                    l[o][j][k] = l[o][j+1][k];
                r[o][j][i] = j;
                for (int k = i; k <= p[i][j+1]; k++)
                    r[o][j][k] = r[o][j+1][k];
                for (int k = max(p[i][j+1], i) + 1; k <= p[i+1][j]; k++)
                    r[o][j][k] = r[o^1][j][k];
                for (int k = i + 1; k <= min(p[i][j+1], p[i+1][j]); k++)
                    if (r[o^1][j][k] >= l[o][j+1][k])
                        s[i][j] -= s[k][l[o][j+1][k]],
                        k = p[k][l[o][j+1][k]];
                ans += 1ll * a[i][j] * (s[i][j] - a[i][j]);
            }
    print(ans);
    return 0;
}