AT_abc183_e [ABC183E] Queen on Grid 题解

· · 题解

前言

特别基础的 DP 题目。

题目分析

首先，这题有三个方向，我们可以分别用三个数组 x、y、z，表示从左边过来有几种方案，从右边过来有几种方案，从斜边过来有几种方案，我们再记 f_{i, j} 为这个走到这个格子有几种方案，可以列出以下式子：

x_{i, j}=x_{1,j}+x_{2, j}+... + x_{i - 1,j}

其他两个方向同理。我们会发现，每次都得再累加 n 次，很不方便，于是我们想到了前缀和。得：

x_{i, j} = x_{i - 1, j} + f_{i,j}

其他两个方向同理，我们又知道，一个能走到一个格子的所有方案数就是三个方向能走过来的方案数加起来，所有的动态转移方程就是：

f_{i,j} = x_{i, j}+y_{i,j}+z_{i,j} x_{i, j} = x_{i - 1, j} + f_{i,j} y_{i, j} = y_{i, j - 1} + f_{i,j} z_{i, j} = z_{i - 1, j - 1} + f_{i,j}

注意先后顺序！最后处理好边界，由于第一个不肯能是障碍物，所以第一个点都是 1。

核心代码

for(int i = 1; i <= n; i ++) 
{
    for(int j = 1; j <= m; j ++) 
    {

        if(ch[i][j] == '.') {
            f[i][j] = (x[i - 1][j] + y[i][j - 1] + z[i - 1][j - 1]) % MOD;

            x[i][j] = (x[i - 1][j] + f[i][j]) % MOD;

            y[i][j] = (y[i][j - 1] + f[i][j]) % MOD;

            z[i][j] = (z[i - 1][j - 1] + f[i][j]) % MOD;
        }
    }
}