「Codeforces 24D」Broken robot

Description

现在有一个机器人，最初站在 $n \times m\ (1 \leq n,m\leq 1000)$ 矩阵中的 $(x,y)\ (1 \leq x \leq n, 1\leq y \leq m)$ 位置。每次它会等概率的选择 原地不动，向左移动，向右移动，向下移动 四种操作。当然，机器人在第 $1$ 列时不会选择向左移动，第 $m$ 列时不会选择向右移动。求机器人到达第 $n$ 行的期望步数，至少精确到 $10^{-4}$ 。

Source

[Luogu]CF24D

[Codeforces]24D

Solution

前置知识：

高斯(Gauss)消元

求期望步数，很容易想到 期望DP 。我们用 $f_{i,j}$ 表示从 $(i,j)$ 走到最后一行的期望步数，那么初始状态就是 $f_{n,i} = 0\ (1 \leq i \leq m)$（从最后一行走到最后一行的期望步数为 $0$），要求的答案就是 $f_{x,y}$（根据状态即能得到），状态转移方程如下（分 $3$ 种情况讨论）：

$$\large{f_{i,j}=\left\{\begin{matrix} \frac{1}{3}\left ( f_{i,j} + f_{i,j+1} + f_{i+1,j} \right )+1& (j=1)\\[2ex] \frac{1}{4}\left ( f_{i,j} + f_{i,j+1} + f_{i,j-1} + f_{i+1,j} \right )+1& (1< j< m) \\[2ex] \frac{1}{3}\left ( f_{i,j} + f_{i,j-1} + f_{i+1,j} \right )+1& (j=m) \\ \end{matrix}\right.}$$

值得注意的是：$m = 1​$ 时比较特殊，因为不能向左和向右移动，此时

$$\large{f_{i,j}=\frac{1}{2} \left( f_{i,j} + f_{i+1,j} \right) + 1}$$

这个转移方程是倒推的，并且有后效性，所以不能直接转移。在求 $f_{i,j}​$ 时，$f_{i+1,j}​$ 是 已知 的，而 $f_{i,j-1},f_{i,j},f_{i,j+1}​$ 都是 未知 的，我们把未知量移到左边，把已知量移到右边，可以得到：

$$\large{\left\{\begin{matrix} -\frac{2}{3}f_{i,j}+\frac{1}{3}f_{i,j+1}=-\frac{1}{3}f_{i+1,j}-1 & (j=1)\\[2ex] \frac{1}{4}f_{i,j-1}-\frac{3}{4}f_{i,j}+\frac{1}{4}f_{i,j+1}=-\frac{1}{4}f_{i+1,j}-1& (1 < j < m)\\[2ex] \frac{1}{3}f_{i,j-1}-\frac{2}{3}f_{i,j}=-\frac{1}{3}f_{i+1,j}-1 & (j=m)\\ \end{matrix}\right.}$$

同理，$m = 1​$ 时，

$$\large{-\frac{1}{2}f_{i,j} = -\frac{1}{2}f_{i+1,j} - 1}$$

我们会发现一共有 $m​$ 个未知数和 $m​$ 个方程，很容易想到 高斯消元 求解未知量 $f_{i,1} \sim f_{i,m}\ (1 \leq i < n)​$ 。

比如说，当 $m = 5​$ 时，所构成的矩阵就是：

$$\large{\begin{bmatrix} -\frac{2}{3} & \color{blue}{\frac{1}{3}} & 0 & 0 & 0\\[1ex] \color{red}{\frac{1}{4}} & -\frac{3}{4} & \color{blue}{\frac{1}{4}} & 0 & 0\\[1ex] 0 & \color{red}{\frac{1}{4}} & -\frac{3}{4} & \color{blue}{\frac{1}{4}} & 0\\[1ex] 0 & 0 & \color{red}{\frac{1}{4}} & -\frac{3}{4} & \color{blue}{\frac{1}{4}}\\[1ex] 0 & 0 & 0 & \color{red}{\frac{1}{3}} & -\frac{2}{3}\\[1ex] \end{bmatrix} =\begin{bmatrix} -\frac{1}{3}f_{i+1,j}-1\\[1ex] -\frac{1}{4}f_{i+1,j}-1\\[1ex] -\frac{1}{4}f_{i+1,j}-1\\[1ex] -\frac{1}{4}f_{i+1,j}-1\\[1ex] -\frac{1}{3}f_{i+1,j}-1\\ \end{bmatrix}}$$

本来 高斯消元 的时间复杂度应该是 $O(n^3)​$ 的。但是观察矩阵能够发现，其实这是一个稀疏矩阵，未知数全部集中在对角线上，$0​$ 的地方不需要消元，我们需要消元的只有 $m - 1​$ 个数（上图 $\color{red}{红色}​$ 的数字），回带时原方程中也只需要消去 $m - 1​$ 个数（上图 $\color{blue}{蓝色}​$ 的数字），所以本题中 高斯消元 时间复杂度为 $O(m)​$ 。总时间复杂度为 $O(nm)​$ 。

Code

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

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

const int MAXN = 1000;
int n, m, x, y;
double a[MAXN + 5][MAXN + 5], f[MAXN + 5][MAXN + 5];

inline void Gauss() {
    for (int i = 1; i < m; ++i) {
        double t = a[i][i];
        a[i][i] = 1;
        a[i][i + 1] /= t;
        a[i][m + 1] /= t;
        t = a[i + 1][i];
        a[i + 1][i] = 0;
        a[i + 1][i + 1] -= t * a[i][i + 1];
        a[i + 1][m + 1] -= t * a[i][m + 1];
    }//消元，消去下一行方程开头的未知数 
    a[m][m + 1] /= a[m][m];
    a[m][m] = 1;//求出最后一个未知数的解 
    for (int i = m - 1; i; --i)
        a[i][m + 1] -= a[i + 1][m + 1] * a[i][i + 1];//回带，消去下一行方程末尾的未知数
}

int main() {
    read(n), read(m), read(x), read(y);
    for (int i = n - 1; i >= x; --i) {
        if (m == 1) {
            a[1][1] = -1.0 / 2;
            a[1][m + 1] = -f[i + 1][1] / 2.0 - 1;//特判 m = 1 
        } else {
            a[1][1] = -2.0 / 3;
            a[1][2] = 1.0 / 3;
            a[1][m + 1] = -f[i + 1][1] / 3.0 - 1.0;
            for (int j = 2; j < m; ++j) {
                a[j][j] = -3.0 / 4;
                a[j][j - 1] = a[j][j + 1] = 1.0 / 4;
                a[j][m + 1] = -f[i + 1][j] / 4.0 - 1;
            }
            a[m][m] = -2.0 / 3;
            a[m][m - 1] = 1.0 / 3;
            a[m][m + 1] = -f[i + 1][m] / 3.0 - 1;
        }//构造矩阵 
        Gauss();//高斯消元 
        for (int j = 1; j <= m; ++j) f[i][j] = a[j][m + 1];//赋值求出的解 
    }
    printf("%.10lf\n", f[x][y]);
    return 0;
}