首页 > 试题广场 >

Bob的生存概率

[编程题]Bob的生存概率

热度指数：895 时间限制：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)