首页 > ACM题库 > HDU-杭电 > hdu 2382 Pachinko-概率计算[解题报告]C++
2014
01-05

hdu 2382 Pachinko-概率计算[解题报告]C++

Pachinko

问题描述 :

Pachinko is a Japanese game played for amusement and prizes, and is similar to pinball.

The game is very simple: you shoot small metal balls into the machine and they fall down, bouncing off the obstacles until they fall into a gate. The gate into which your ball falls determines the winnings.

Since you can more or less determine the column into which the ball is dropped (by setting its initial speed and direction), you can influence your win chances. You are to calculate your expected winnings.

We model the pachinko machine as follows: you can drop the ball in any column and it falls down until it either reaches the bottom of the machine (which results in no wins), a gate (indicated by a number 1 to 9, which results in that win) or an obstacle (indicated by a asterisk). If a ball hits an obstacle it proceeds falling in the column to the left or to the right of the obstacle, with 50/50 probability. No two obstacles or gates are adjacent, not even diagonally, and none is located in the leftmost or rightmost column.

输入:

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with two integers h and w (1 <= h,w <= 100): the height and width of the pachinko machine.

h lines with w characters describing the pachinko machine. A ‘.’ denotes an empty space, ‘*’ an obstacle and ’1′. . . ’9′ the winning gates.

输出:

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with two integers h and w (1 <= h,w <= 100): the height and width of the pachinko machine.

h lines with w characters describing the pachinko machine. A ‘.’ denotes an empty space, ‘*’ an obstacle and ’1′. . . ’9′ the winning gates.

样例输入:

3
7 5
.....
.1...
...2.
.*...
.....
.....
..5..
8 8
...1....
........
..*...*.
....*...
.1......
...*.*..
........
..9.7.7.
10 10
.*.*.*.*..
..........
..*.*.*.*.
..........
.*.*.*.*..
..........
..*.*.*.*.
..........
.*.*.*.*..
....9.....

样例输出:

5.000000
7.500000
3.375000

【全文翻译】

弹球游戏

弹球游戏是一款集娱乐和奖励的日本游戏,类似于三维弹球。

游戏很简单:你发射一个小金属球到机器里,通过挡板和障碍物的反弹,直到掉进洞口。球掉在哪个洞里决定了你的奖金。

既然你可以或多或少的决定金属球从哪个入口进入(通过设定球的初始速度和方向),你可以提高你的获胜几率。你耀计算你的预期奖金。

我们建立弹球游戏的模型如下:你可以让金属球从任何入口进入,球会掉到机器底部(不会赢得奖励),也会掉到洞里(由数字1到9表示,会赢得奖励),还会撞到障碍物上(由1个星号表示)。如果金属球撞到障碍上它会向左或向右掉下去,各有50%的概率。没有两个相邻的洞或者障碍,甚至对角,也没有在最左边或最右边的入口。

输入

第一行的一个整数t(1<=t<=100):要输入的个数。然后输入每个测试数据:

一行两个整数h和w(1<=h,w<=100):表示弹球游戏机的高度和宽度。

h行和w用来绘制弹球游戏机。一个“.”表示一个空的空间,一个“*”表示障碍,“1”……“9”表示可赢得奖金的洞。

输出

对于每个测试数据:

一行为预期的最大奖金和一个最大为10-6的相对或绝对误差。

#include <stdio.h>
#include <string.h>
#define N 110
#define eps 1e-8

char map[N][N];
double visit[N][N]; //到该点的概率

double deal ( int c, int n, int m ) {
 int i, j;
 double ans = 0;
 memset ( visit, 0, sizeof ( visit ) );
 visit[ 0 ][ c ] = 1;
 for ( i = 0 ; i < n - 1 ; ++i ) { //这里用的是向下扩展
  for ( j = 0 ; j < m ; ++j ) {
   if ( visit[ i ][ j ] > eps ) {
    if ( map[ i ][ j ] != '.' ) { //有概率就一定不是'*' 并且又不是'.'的情况下就是数字了
     ans += visit[ i ][ j ] * ( map[ i ][ j ] - '0' );
    }
    else {
     if ( map[ i + 1 ][ j ] != '*' ) { //不是'*'的地方直接继承
      visit[ i + 1 ][ j ] += visit[ i ][ j ];
     }
     else {
      if ( j > 0 ) { //向左下右下扩展
       visit[ i + 1 ][ j - 1 ] += visit[ i ][ j ] / 2;
      }
      if ( j < m - 1 ) {
       visit[ i + 1 ][ j + 1 ] += visit[ i ][ j ] / 2;
      }
     }
    }
   }
  }
 }
 for ( i = 0 ; i < m ; ++i ) { //最后一行特别处理下
  if ( map[ n - 1 ][ i ] != '*' && map[ n - 1 ][ i ] != '.' ) {
   ans += visit[ n - 1 ][ i ] * ( map[ n - 1 ][ i ] - '0' );
  }
 }
 return ans;
}

int main () {
 int i, n, m, t;
 double ans, temp;
 scanf ( "%d", &t );
 while ( t-- ) {
  scanf ( "%d%d", &n, &m );
  getchar();
  for ( i = 0 ; i < n ; ++i ) {
   gets( map[ i ] );
   if ( map[ i ][ 0 ] == '\0' ) --i;
  }
  ans = 0;
  for ( i = 0 ; i < m ; ++i ) {
   if ( map[ 0 ][ i ] != '.' ) { //特判下第一行
    if ( map[ 0 ][ i ] == '*' ) temp = 0;
    else temp = map[ 0 ][ i ] - '0';
   }
   else temp = deal( i, n, m ); //向下搜索
   if ( temp - ans > eps ) ans = temp;
  }
  printf ( "%.6lf\n", ans );
 }
 return 0;
}