题解 CF1225E 【Rock Is Push】

· · 题解

感觉这题非常有趣，尤其是这个样例解释。

这个问题形式上类似格线游走，虽然无法直接使用格线游走的模型解决，仍然可以考虑 DP。

考虑到我们只能向右或向下走，那么如果我们在某一步向右推了一块石头，那么它右边的石头一定都没动过。这启发我们在 DP 中记录最后一步向哪一个方向走。

如果我们仍然一步一步转移，那么会产生一个问题——我们无法得知走到 (i,j) 时，从那个方向推了多少块石头过来。

但是我们又注意到我们在判断 (i,j) 能否向右走的时候只关心我们从 (i,j) 左侧推了多少块石头过来，而如果我们在游走过程中从 (k,j-1) 走到 (k,j) 再走到 (i,j) 其中 k<i，那么 (k,j) 左侧的所有石头都不可能被推到 (i,j)，而 (k,j) 右侧的所有石头都一定被推到 (i,j)，因为如果这些石头被动过，那么一定在一个时刻游走到了 x 坐标 >k 的位置，再走回 (k,j)，与只能向下向右矛盾。

这启发我们枚举最后的连续一段向一个方向走，然后强制上一步往另外一个方向走。可以转移当且仅当最后走的一段上面的石头能够全部被推到目标点下方。

直接转移是 O(nm(n+m))，无法通过。但是容易使用前缀和优化到 O(nm)。

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

const int mod = 1000000007;
int n, m, dp[2][2005][2005], pres[2][2005][2005];
char mp[2005][2005];
vector <int> rrk[2005], crk[2005];

inline void Read() {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) cin >> mp[i][j];
    }
}

inline void Prefix() {
    for (int i = n;i >= 1;i--) {
        for (int j = m;j >= 1;j--) {
            if (mp[i][j] == 'R') {
                rrk[i].push_back(j);
                crk[j].push_back(i);
            }
        }
    }
}

inline void Solve() {
    if (n == 1 && m == 1) {
        cout << 1 << endl;
        return;
    }
    dp[0][1][1] = dp[1][1][1] = 1;
    pres[0][1][1] = pres[1][1][1] = 1;
    for (int i = 1;i <= n;i++) {
        for (int j = 1 + (i == 1);j <= m;j++) {
            int lst;
            if (m - j >= rrk[i].size()) lst = 1;
            else lst = rrk[i][m - j];
            dp[0][i][j] = (pres[1][i][j - 1] - pres[1][i][lst - 1] + mod) % mod;
            if (n - i >= crk[j].size()) lst = 1;
            else lst = crk[j][n - i];
            dp[1][i][j] = (pres[0][i - 1][j] - pres[0][lst - 1][j] + mod) % mod;
            pres[1][i][j] = (pres[1][i][j - 1] + dp[1][i][j]) % mod;
            pres[0][i][j] = (pres[0][i - 1][j] + dp[0][i][j]) % mod;
        }
    }
    cout << (dp[0][n][m] + dp[1][n][m]) % mod << endl;
}

int main() {
    std::ios::sync_with_stdio(0);
    Read();
    Prefix();
    Solve();
    return 0;
}