CF1840F Railguns

这篇博客介绍了使用动态规划算法解决一个机器人在网格中避开激光炮到达终点的最短路径问题。

题意

Tema在 $n×m$ 的网格内要从 $(0,0)$ 走到 $(n,m)$。第0秒Tema位于 $(0,0)$。
假设第 $t$ 秒Tema位于 $(i,j)$，则第 $t+1$秒Tema可以在 $(i,j)$， $(i+1,j)$ 或 $(i,j+1)$.
机器人会发射 $r$ 次激光炮阻挠他的前进，每次发射会在某一秒攻击某一列或某一行，若该秒Tema在被攻击的单元格内，则会被击毁。求Tema从 $(0,0)$ 到达 $(n,m)$ 所需的最短时间，若无法抵达则输出 $-1$。

思路

首先，不难发现最少需要 $i+j$ 秒、最多需要 $i+j+r$ 秒可以到达点 $(i,j)$。令 $dp[i][j][k]$ 表示在第 $i+j+k$ 秒时Tema能否在 $(i,j)$ 上，则转移方程为 $dp[i][j][k]=dp[i-1][j][k]|dp[i][j-1][k]|dp[i][j][k-1]$，且如果第 $i+j+k$ 秒时 $(i,j)$ 受到攻击，则$dp[i][j][k]$ 为 $0$ 。最后枚举所有的 $dp[n][m][k]$ 即可。

代码

void solve() {
    int n, m, r;
    cin >> n >> m >> r;
    bool dp[n + 10][m + 10][r + 10] = {0}, b[n + 10][m + 10][r + 10];
    mem(dp, 0);
    mem(b, 1);
    rep(j, 0, r - 1) {
        int t, d, co;
        cin >> t >> d >> co;
        if (d == 1) {
            rep(i, 0, m) {
                if (t - co - i >= 0 && t - co - i <= r)
                    b[co][i][t - co - i] = 0;
            }
        } else if (d == 2) {
            rep(i, 0, n) {
                if (t - co - i >= 0 && t - co - i <= r)
                    b[i][co][t - co - i] = 0;
            }
        }
    }
    dp[0][0][0] = 1;
    rep(i, 0, n) rep(j, 0, m) rep(k, 0, r) {
        if (i > 0)
            dp[i][j][k] |= dp[i - 1][j][k];
        if (j > 0)
            dp[i][j][k] |= dp[i][j - 1][k];
        if (k > 0)
            dp[i][j][k] |= dp[i][j][k - 1];
        dp[i][j][k] &= b[i][j][k];
    }
    rep(i, 0, r) {
        if (dp[n][m][i]) {
            cout << n + m + i << endl;
            return;
        }
    }
    cout << "-1\n";
    return;
}