Bob还在棋盘中的概率

本文主要是介绍Bob还在棋盘中的概率，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：给定5个参数，N，M，row，col，K，表示在N*M的区域上，醉汉Bob初始在（row,col）位置，Bob一共要迈出K步，且每步都会等概率向上下左右的4个方向之一走一个单位，任何时候Bob只要离开N * M区域，就直接死亡，返回K步之后，Bob还在N * M区域中的概率。

way：初始在某点的概率=在某点可以生存下来的路线数/在某点可以走的总路线数(4的K次方）（K步）。

#include<iostream>
#include<vector>
using namespace std;//目前在row, col位置，还有rest步要走，走完之后如果还在棋盘中就获得一种生存路线方案，返回总的生存方案数
long 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;int ways=0;ways+=process(row-1, col, rest-1, N, M);ways+=process(row+1, col, rest-1, N, M);ways+=process(row, col-1, rest-1, N, M);ways+=process(row, col+1, rest-1, N, M);return ways;
}double livePosibility1(int row, int col, int K, int N, int M)
{return (double)process(row,col,K,N,M)/pow(4,K);
}

way2：dp版

//改dp
long long pick(int x, int y, int rest, int N, int M, vector<vector<vector<long long>>>dp)
{//超出区域，死if(x<0 || x==N || y<0 || y==M){return 0;}return dp[x][y][rest];
}double livePosibility2(int row, int col, int K, int N, int M)
{vector<vector<vector<long long>>>dp(N, vector<vector<long long>>(M, vector<long long>(K+1)));for(int i=0; i<N; i++){for(int j=0; j<M; j++){dp[i][j][0]=1;}}for(int rest=1; rest<=K; rest++){for(int i=0; i<N; i++){for(int j=0; j<M; j++){long long ways=0;ways+=pick(i-1, j, rest-1, N, M, dp);ways+=pick(i+1, j, rest-1, N, M, dp);ways+=pick(i, j-1, rest-1, N, M, dp);ways+=pick(i, j+1, rest-1, N, M, dp);dp[i][j][rest]=ways;}}}return (double)dp[row][col][K]/pow(4,K);
}

这篇关于Bob还在棋盘中的概率的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---