首页 > 试题广场 >

Bob的生存概率

[编程题]Bob的生存概率

热度指数：888 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定五个参数n,m,i,j,k。表示在一个n*m的区域，Bob处在(i,j)点，每次Bob等概率的向上、下、左、右四个方向移动一步，Bob必须走k步。如果走完之后，Bob还停留在这个区域上，就算Bob存活，否则就算Bob死亡。请求解Bob的生存概率，返回字符串表示分数的方式。

输入描述:

输入一行5个整数:n，m，i，j，k

输出描述:

输出一行字符串代表Bob的生存概率

示例1

输入

10 10 3 2 5

输出

945/1024

算法知识视频讲解

JavaScript

singletouch

var args = readline().split(' ');

var n = parseInt(args[0]),
	m = parseInt(args[1]),
	i = parseInt(args[2]),
	j = parseInt(args[3]),
	k = parseInt(args[4]);

var prePoints = [[i,j,1]];
var curPoints = [];

function isInArea (pointX, pointY) {
	if(pointX >= 0 && pointX < n && pointY >= 0 && pointY < m) {
		return 1
	}
	return 0;
}

function checkAndPushPoint (pointX, pointY, count) {
	if(isInArea(pointX, pointY)) {
		var item = curPoints.find((item) => item[0] == pointX && item[1] == pointY);
		if(item) {
			item[2] += count;
		} else {
			curPoints.push([pointX, pointY, count])
		}
	}
}


for(var s = 1; s <= k; s++) {
	for(var p = 0, len = prePoints.length; p < len; p++) {
		var point = prePoints[p];
		var x = point[0], y = point[1], count = point[2];

		checkAndPushPoint(x-1,y,count);
		checkAndPushPoint(x+1,y,count);
		checkAndPushPoint(x,y-1,count);
		checkAndPushPoint(x,y+1,count);
	}
	prePoints = curPoints;
	curPoints = [];
}


var path = 0;

for(var p = 0, len = prePoints.length; p < len; p++) {
	path += prePoints[p][2];
}


var total = Math.pow(4,k);
var gcd = gcd(path,total);

function gcd(m, n) {
    return n == 0 ? m : gcd(n, m % n);
}

console.log(`${path/gcd}/${total/gcd}`)

编辑于 2022-11-09 16:54:03 回复(0)

牛客908435449号

import java.util.*;

public class Main {
    public static int n=0;
    public static int m=0;
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();
        int steps = sc.nextInt();
        long[][][] dp = new long[n][m][steps+1];
        dp[x][y][0] = 1;
        for(int l=1; l<=steps; l++){
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    dp[i][j][l] += getValue(dp,l-1,i-1,j);
                    dp[i][j][l] += getValue(dp,l-1,i+1,j);
                    dp[i][j][l] += getValue(dp,l-1,i,j-1);
                    dp[i][j][l] += getValue(dp,l-1,i,j+1);
                }
            }
        }
        long res = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                res += dp[i][j][steps];
            }
        }
        long total = (long)Math.pow(4,steps);
        long gcd = gcd(res,total);
        String s = (res/gcd)+"/"+(total/gcd);
        System.out.println(s);
    }
    
    public static long getValue(long[][][] dp,int l,int x,int y){
        if(x<0 || x>=n || y<0 || y>=m){
            return 0;
        }
        return dp[x][y][l];
    }
    
    public static long gcd(long m, long n) {
        return n == 0 ? m : gcd(n, m % n);
    }
}

发表于 2022-02-03 12:29:33 回复(0)