题解：P6899 [ICPC2014 WF] Pachinko

Rr_haril · 2024-10-08 13:54:13 · 题解

蒟蒻来发题解了

DP写法

定义状态 dp_{i,j} 为从顶部发射的球最终到达坐标 (i , j) 的概率。依题意，球在每个格子上有四种可能的移动方向，分别是上、下、左、右，移动的概率分别为 u 、 d 、 l 、 r 。需要依据这些概率来更新每个格子的概率。

状态转移方程：

若当前格子为 X，则 dp_{i,j} = 0 。
若当前格子为 T，则 dp_{i,j} 保持不变，因为我们只关心目标被击中的概率。
若当前格子为 .，则根据方程更新：

dp_{i,j} = \frac{u}{100} \cdot dp_{i-1,j}+ \frac{ d }{ 100 } \cdot dp_{i+1,j}+ \frac{l}{100} \cdot dp_{i,j-1}+ \frac{ r }{ 100 } \cdot dp_{i,j+1}

代码实现

#include <bits/stdc++.h>
using namespace std;

/* 定义最大高度和宽度 */
const int   maxh = 10000, maxw = 20;
int     w, h;

/* 定义四个方向的偏移量 */
const int d[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

/* 定义网格地图 */
char mp[maxh + 5][maxw + 5];

/* 定义系数矩阵和解向量 */
double c[maxh * maxw + 5][2 * maxw + 5];
double & fc( int i, int j )
{
    return(c[i][j + w - i]);
}

double sol[maxh * maxw + 5];

int main()
{
/* 读取网格的宽度和高度 */
    scanf( "%d%d", &w, &h );

/* 读取四个方向的概率 */
    double p[4];
    for ( int i = 0; i < 4; i++ )
        scanf( "%lf", &p[i] ), p[i] /= 100;

/* 读取网格地图 */
    for ( int i = 1; i <= h; i++ )
        scanf( "%s", mp[i] + 1 );

/* 计算顶部开放空间的数量 */
    int c1 = 0;
    for ( int i = 1; i <= w; i++ )
        if ( mp[1][i] == '.' )
            c1++;

/* 定义方向对应的偏移量 */
    int pos[4] = { -w, w, -1, 1 };
/* 初始化系数矩阵和解向量 */
    for ( int i = 1; i <= h; i++ )
        for ( int j = 1; j <= w; j++ )
        {
            int id = (i - 1) * w + j;
            if ( mp[i][j] == 'X' )
                continue;
            fc( id, id ) = -1;
            if ( i == 1 && mp[i][j] == '.' )
                sol[id] = 1. / c1;
            for ( int dir = 0; dir < 4; dir++ )
            {
                int x = i + d[dir][0], y = j + d[dir][1];
                if ( mp[x][y] == '.' )
                    fc( id, id + pos[dir] ) += p[dir ^ 1];
                else if ( mp[x][y] != 'T' && mp[i][j] == '.' )
                    fc( id, id ) += p[dir];
            }
        }

/* 高斯消元法求解线性方程组 */
    for ( int i = 1; i <= h * w; i++ )
    {
        if ( fabs( fc( i, i ) ) == 0 )
            continue;
        for ( int j = i + 1; j <= min( i + w, h * w ); j++ )
        {
            double t = fc( j, i ) / fc( i, i );
            for ( int k = i; k <= min( i + w, h * w ); k++ )
                fc( j, k ) -= fc( i, k ) * t;
            sol[j] -= sol[i] * t;
        }
    }

/* 回代求解 */
    for ( int i = h * w; i > 0; i-- )
    {
        if ( fabs( fc( i, i ) ) == 0 )
            continue;
        for ( int j = i + 1; j <= min( i + w, h * w ); j++ )
            sol[i] += fc( i, j ) * sol[j];
        sol[i] /= -fc( i, i );
    }

/* 输出每个目标的概率 */
    for ( int i = 1; i <= h; i++ )
        for ( int j = 1; j <= w; j++ )
            if ( mp[i][j] == 'T' )
                printf( "%.8lf\n", sol[(i - 1) * w + j] );
}

题解：P6899 [ICPC2014 WF] Pachinko

蒟蒻来发题解了

DP写法

代码实现

管理大大求过