问题描述

给定 5 个参数，N、M、row、col、k 。在 NM 的区域上，醉汉 Bob 初始在 (row,col) 位置。Bob一共需要迈出 k 步，且每步都会等概率向上、下、左、右四个方向走一个单位。任何时候 Bob 只要离开 NM 的区域，就直接死亡。返回 k 步之后，Bob 的死亡率。

暴力递归

和 动态规划-杀死那怪兽 类似，也是求概率问题。我在那篇文章末尾留下了一个疑问——为什么要鞭尸？这个疑问在本题中能够很好地举例体现。假设条件为：N=M=2 ，row=col=1 ，k = 30 ，如果 Bob 死亡后不再进行后续移动，那么最后得到的死亡概率为 0.66 。这显然是错误的，死亡率率应该比 0.66 要大得多。所以本题也必须鞭尸，总走法有 4^k 种 ，死亡率 = 死法/总走法 。

借鉴 动态规划-杀死那怪兽 中的做法（死亡率=1-生存率），我们将求死亡率转换为求生存率，从而避免鞭尸带来的麻烦。

double process(int row, int col, int rest, int N, int M)
{
    if (row < 0 || row == N || col < 0 || col == M)
        return 0;
    if (rest == 0)
        return 1;
    double up   = process(row - 1, col, rest - 1, N, M);
    double down = process(row + 1, col, rest - 1, N, M);
    double left = process(row, col - 1, rest - 1, N, M);
    double right= process(row, col + 1, rest - 1, N, M);
    return up + down + left + right;
}

double livePosibility(int row, int col, int k, int N, int M)
{
    return 1 - process(row, col, k, N, M) / pow(4, k);
}

动态规划

水到渠成，不再赘述

double help(vector<vector<vector<double>>>& dp, int N, int M, int r, int c, int rest) {
    if (r < 0 || r == N || c < 0 || c == M) 
        return 0;
    if (rest == 0)
        return 1;
    return dp[r][c][rest];
}
double livePosibility(int row, int col, int k, int N, int M) 
{
    vector<vector<vector<double>>> dp(N, vector<vector<double>>(M, vector<double>(k + 1, 0)));
    for (int rest = 1; rest <= k; rest++)
    {
        for (int r = 0; r < N; r++)
        {
            for (int c = 0; c < M; c++)
            {
                dp[r][c][rest] =  help(dp, N, M, r - 1, c, rest - 1);
                dp[r][c][rest] += help(dp, N, M, r + 1, c, rest - 1);
                dp[r][c][rest] += help(dp, N, M, r, c - 1, rest - 1);
                dp[r][c][rest] += help(dp, N, M, r, c + 1, rest - 1);
            }
        }
    }
    return 1 - (double)dp[row][col][k] / pow(4, k);
}