牛客网--蘑菇阵

本文主要是介绍牛客网--蘑菇阵，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

现在有两个好友A和B，住在一片长有蘑菇的由n＊m个方格组成的草地，A在(1,1),B在(n,m)。现在A想要拜访B，由于她只想去B的家，所以每次她只会走(i,j+1)或(i+1,j)这样的路线，在草地上有k个蘑菇种在格子里(多个蘑菇可能在同一方格),问：A如果每一步随机选择的话(若她在边界上，则只有一种选择)，那么她不碰到蘑菇走到B的家的概率是多少？
输入描述:

第一行N，M，K(1 ≤ N,M ≤ 20, k ≤ 100),N,M为草地大小，接下来K行，每行两个整数x，y，代表(x,y)处有一个蘑菇。

输出描述:

输出一行，代表所求概率(保留到2位小数)

示例1

输入

2 2 1
2 1

输出

0.50

分析：

首先想到的办法是，求出从左上角到右下角所有的路径数目，以及不包含一颗蘑菇的路径数目，二者相除，便得到了A碰不到蘑菇走到B的家的概率，这可以用DFS来解决，三下五除二，就一个DFS出来了：

void AwalkDFS(vector<vector<int>> &Map,int i,int j,int PathMushromCount,int &A,int &B){
/*Map：地图i,j:当前位置A:到达右下角没有蘑菇的路径数B:到达右下角有蘑菇的路径数
*/if (i >= 0 && i < Map.size() && j >= 0 && j < Map[0].size()){if (i == Map.size() && j == Map[0].size()){PathMushromCount+Map[i][j]>0 ? ++B : ++A;return;}AwalkDFS(Map, i, j + 1, PathMushromCount + Map[i][j], A, B);//toward the rightAwalkDFS(Map, i+1, j, PathMushromCount + Map[i][j], A, B);//toward the down}
}

完全是瞎做！这样的DFS 是指数时间，因为要穷举所有的可能，没有剪枝，别说答案是否正确，就连时间都不允许！

于是乎，稍加思考，就可以改进为动态规划：

(1) 假设 $f_{ij}$ 表示到达 $Map[i][j]$ 的总路径数目，由于每一步只能想右或向下，则它依赖于左边和上边的状态，即到达 $f_{ij}$ 的路径数等于到达左边 $f_{i,j-1}$ 的路径数加上到达到 $f_{i-1, j}$ 的路径数：

f i j = {f i - 1, j + f i, j - 1, i > = 1, j > = 1 1, i = 0 o r j = 0 (1)

$f_{ij}=\left\{ \begin{array}{l} f_{i-1,j}+f_{i,j-1},i>=1,j>=1 \\ 1, i=0 \ or \ j=0\\ \end{array} \right. \tag{1}$

(2) 假设 $h_{ij}$ 表示走到 $Map[i][j]$ 没有遇到蘑菇的路径数目，类似于 $f_{ij}$ 的分析，它依赖于 $Map[i][j]$ 的状态，及 $h_{i-1,j}$ 、 $h_{i,j-1}$ ,状态方程如下

h i, j = ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ 0, i = j = 0, M a p [0] [0] = 0, (左 上 角 格 子) 0, M a p [i] [j] > 1, (如 果 某 个 格 子 有 蘑 菇 ， 则 到 此 格 不 遇 到 蘑 菇 的 路 径 数 目 为 0) h i - 1, j + h i, j - 1, i > = 1, j > = 1, (此 格 子 没 蘑 菇, 等 于 上 + 左) h 0, j - 1, i = 0, (边 界 条 件 ， 第 一 行) h i - 1, 0, j = 0, (边 界 条 件 ， 第 一 列) (2)

$h_{i,j}=\left\{ \begin{array}{l} 0,i=j=0,Map[0][0]=0,(左上角格子)\\ 0,Map[i][j]>1,(如果某个格子有蘑菇，则到此格不遇到蘑菇的路径数目为0)\\ h_{i-1,j}+h_{i,j-1} ,i>=1 , j>=1,(此格子没蘑菇,等于上+左)\\ h_{0,j-1},i=0,(边界条件，第一行)\\ h_{i-1,0},j=0,(边界条件，第一列)\\ \end{array} \right. \tag{2}$
按照这样的思路，写出代码

double AWalk_dp_1(vector<vector<int>> &Map){int N = Map.size();if (N == 0) return 0;int M = Map[0].size();vector<vector<int>> P(N, vector<int>(M, 0));//fijvector<vector<int>> H = P;  //hij/*initializing*/P[0][0] = 1; H[0][0] = 1;//************1. initialize the first column**************for (int i = 1; i<N; ++i){P[i][0] = 1;H[i][0] = H[i - 1][0];if (Map[i][0]>0) H[i][0] = 0;}//************2. initialize the first row**************for (int j = 1; j<M; ++j){P[0][j] = 1;H[0][j] = H[0][j - 1];if (Map[0][j]>0) H[0][j] = 0;}for (int i = 1; i<N; ++i)for (int j = 1; j<M; ++j){P[i][j] = P[i - 1][j] + P[i][j - 1];if (Map[i][j]>0) H[i][j] = 0;else{H[i][j] = H[i - 1][j] + H[i][j - 1];}}return (double)H[N - 1][M - 1] / P[N - 1][M - 1];
}

然而求解的结果任然是错误的，不过，求解的路径数目是正确的！而且求解路径数目的速度降到了 $O(NM)$ !

进一步分析题目发现，其实发现A走到每一个格子的概率P是不一样的，拿其中一个算例来分析，如图所示：

比如边界上的格子:
(1) 左上角Map[0][0]=0, 到达的概率是1;
(2) 第一行，对于任意P[0][j],它只能从左边一格到达，如果格子仅有一行，A在Map[0][j] 的时候只能走到Map[0][j+1]。
其余边界分析类似…..

对于最右下角（目标）格子，格子Map[N-1][M-2] (下标从0开始)、Map[N-2][M-1] 都只能以1的概率到达此格子。

基于这样的分析，假设 $g_{ij}$ 表示 $A$ 到达格子 $Map[i][j]$ 不碰见蘑菇的概率，同样，除去边界，它可以由 $g_{i-1,j}$ 及 $g_{i,j-1}$ 表示，所以有以下的状态方程

g i j = ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ 1, i = j = 0, (第 一 个 格 子 不 能 有 蘑 菇 ， 否 则 后 面 都 不 用 打 算 了) 0 ， M a p [i] [j] > 0, (若 某 个 格 子 有 蘑 菇 ， 则 到 达 此 格 子 不 碰 到 蘑 菇 的 概 率 为 0) 1 2 g i - 1, j + 1 2 g i, j - 1, i > = 1, j > = 1 1 2 g 0, j - 1, i = 0, j > = 1, N > 1, (上 图 中 第 一 行 绿 色 区 域) g 0, j - 1, i = 0, j > = 1, N = 1, (仅 一 行 时 左 边 格 只 能 向 右 ， 即 以 1 的 概 率 到 达 (i, j)) 1 2 g i - 1, 0, j = 0, i > = 1, M > 1 (上 图 中 第 一 列 绿 色 区 域) g i - 1, 0, j = 0, i > = 1, M = 1, (仅 一 列 时 左 边 格 只 能 向 下 ， 即 以 1 的 概 率 到 达 (i, j)) g i - 1, j + g i, j - 1, i = N - 1, j = M - 1, N, M > 1, (图 中 的 目 标 格 子)

$g_{ij}=\left\{ \begin{array}{l} 1 ,i=j=0,(第一个格子不能有蘑菇，否则后面都不用打算了)\\ 0，Map[i][j]>0,(若某个格子有蘑菇，则到达此格子不碰到蘑菇的概率为0)\\ \frac{1}{2}g_{i-1,j}+\frac{1}{2}g_{i,j-1},i>=1,j>=1\\ \frac{1}{2}g_{0,j-1},i=0,j>=1,N>1,(上图中第一行绿色区域)\\ g_{0,j-1},i=0,j>=1,N=1,(仅一行时左边格只能向右，即以1的概率到达(i,j))\\ \frac{1}{2}g_{i-1,0},j=0,i>=1,M>1(上图中第一列绿色区域)\\ g_{i-1,0},j=0,i>=1,M=1,(仅一列时左边格只能向下，即以1的概率到达(i,j))\\ g_{i-1,j}+g_{i,j-1},i=N-1,j=M-1,N,M>1,(图中的目标格子)\\ \\ \end{array} \right.$

上面状态方程看似繁杂，但核心思想只有一个：

g i j 由 g i - 1, j 及 g i, j - 1 转 换 而 来

$g_{ij}由g_{i-1,j}及g_{i,j-1}转换而来$

只不过不同的位置，这个转换概率不同，所以导致了一系列边界的处理。
最终的代码如下（牛客网测试通过，上图就是所得出的动态规划表数据）：

double AWalk_dp(vector<vector<int>> &Map){int N = Map.size();if (N == 0) return 0.0;int M = Map[0].size();if (M == 0) return 0.0;vector<vector<double>> P(N, vector<double>(M, 0));/*initializing*/P[0][0] = 1; //************1. initialize the first column**************for (int i = 1; i<N; ++i){if (M>1) P[i][0] = P[i-1][0]*0.5;else  P[i][0] = P[i - 1][0] * 1.0;if (Map[i][0]>0) P[i][0] = 0.0;}//************2. initialize the first row**************for (int j = 1; j<M; ++j){if (N>1) P[0][j] = P[0][j-1]*0.5;else     P[0][j] = P[0][j - 1] * 1.0;if (Map[0][j]>0) P[0][j] = 0.0;}//************3. calculate no-boundary area ***********for (int i = 1; i<N-1; ++i)for (int j = 1; j<M-1; ++j){if (Map[i][j]>0) P[i][j] = 0.0;else  P[i][j] = 0.5*(P[i - 1][j] + P[i][j - 1]);}//***********4 coping with boundary*********for (int i = 1,j=M-1; j>0 && i < N-1; i++){P[i][j] = 0.5 * P[i][j-1] + P[i - 1][j];if (Map[i][j]>0) P[i][j] = 0.0;}for (int j = 1,i=N-1;i>0 && j < M-1; j++) {P[i][j] = 0.5*P[i - 1][j] + P[i][j-1];if (Map[i][j]>0) P[i][j] = 0.0;}if (N>1 && M>1)P[N - 1][M - 1] =1.0 * P[N-2][M-1] + 1.0*P[N-1][M-2];return  P[N-1][M-1];
}