2014
01-05

# 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

【全文翻译】

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

#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;
}