HDU 3853 LOOPS 概率dp入门 (一)

HDU 3853 LOOPS 概率dp入门 (1)

/**
*   Author : johnsondu
*	time: 2012-10-13-9:30 around
*	url: http://acm.hdu.edu.cn/showproblem.php?pid=3853
*	stratege: 概率dp
**/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std ;

#define eps 1e-10
#define M 1005
double dp[M][M] ;
double p[M][M][3] ;  // 三维,因为每个当前位置有3种走法(当前位置[r][c]),[r][c], [r+1][c], [r][c+1] ;
int r, c ;

double Abs (double t)
{
	return t < 0 ? -t : t ;
}


int main ()
{
	int i, j, k ;
	while (scanf ("%d%d", &r, &c) != EOF)
	{
		for (i = 0; i < r; i ++)
			for (j = 0; j < c; j ++)
			{
				for (k = 0; k < 3; k ++)
					scanf ("%lf", &p[i][j][k]) ; //0--[r][c],  1--[r][c+1], 2--[r+1][c]
				dp[i][j] = 0 ;
			}
		//dp[i][j] = p[i][j][0]*dp[i][j] + p[i][j][1] * dp[i][j+1] + p[i][j][2]*dp[i+1][j] + 2
		// -->  dp[i][j] = (p[i][j][1] * dp[i][j+1] + dp[i+1][j]*p[i][j][2] + 2) / (1-p[i][j][0])
		// 注意: 1-p[i][j][0] > 0 ;
		for (i = r-1; i >= 0; i --)
			for (j = c-1; j >= 0; j --)
			{
				if (i == r-1 && j == c-1) continue ;
				if (Abs (1-p[i][j][0] < eps)) continue ;
				dp[i][j] = (p[i][j][1] * dp[i][j+1] + dp[i+1][j]*p[i][j][2] + 2) / (1-p[i][j][0])  ;
			}
		printf ("%.3lf\n", dp[0][0]) ;
	}
	return 0 ;
}