8696: BZOJ4696:文明

Memory Limit:10 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

红学姐和黄学长是好朋友。 红学姐有一只宠物,叫魔法猪。黄学长也有一只宠物,叫小奇。有一天,小奇来到了一个古老的文明的遗址上。这 个文明曾经的统治者被称作“战狂”,他生前有一千万士兵。这片土地被划分成 n×m 个正方形方块,初始时小奇 在(1,1)这个方块中。而在(n,m)这个方块中有一个远古遗迹。当小奇在(i,j)时,它分别有Pi,j,1 ,Pi,j,2 ,Pi,j, 3 ,Pi,j,4 的概率移动到(i-1,j),(i,j+1),(i+1,j),(i,j-1)。此外,在一些格子中存在“蛮子”,如果小奇走到 蛮子所在的格子里,它会被蛮子生吃掉。当小奇得到远古遗迹时,它就会停止移动,并让魔法猪把它传送走(当然 如果它被蛮子吃了也会停止移动)。小奇想知道它得到远古遗迹的概率,被蛮子吃掉的概率以及再也停不下来的概 率。


输入格式

第一行包含两个整数 n,m,其值均小于等于40 接下来 n*m 行按上题的编号顺序依次表示每个格子。每行 5 个数,第一个数为 0 表示没有蛮子,为 1 表示有蛮 子,后面 4 个数(至多小数点后 1 位)表示 Pi,j,1 ,Pi,j,2 ,Pi,j,3 ,Pi,j,4 。保证(1,1)和(n,m)没有蛮子。


输出格式

输出三行,每行一个实数,分别表示小奇得到远古遗迹的概率,被蛮子吃掉的概率以及再也停不下来的概率。保留  4 位小数。


样例输入

4 3
0 0 0.2 0.8 0
0 0 0.3 0.7 0
0 0 0 0.5 0.5
0 0 0.2 0.8 0
0 0.2 0.8 0 0
0 1 0 0 0
0 0 1 0 0
0 0.3 0.4 0.3 0
0 0 0 1 0
1 0 1 0 0
0 0 0.7 0 0.3
0 1 0 0 0

样例输出

0.3904
0.0576
0.5520

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: