题解：P16584 [GKS 2016 #C] Monster Path

· · 题解

Analysis

首先来看期望的计算。由期望的线性性可得，整条路径上的总期望等于路径上所以被访问过的格子的期望总和。对于某一个格子，我们设在整个路径中一共经过了 t 次，且该格子的一次成功概率为 p'（若为 A 则 p'=P，否则 p'=Q）。单次的失败概率为 1-p'，t 次的失败概率为 (1-p')^t，那么 t 次至少成功一次的概率即为 1-(1-p')^t。同理总期望即为 \sum\limits_{i\in path} 1-(1-p'_i)^t。

单个路径的计算有了，接下来就是要暴力搜索所有可能的路径。由于 S\le9，那总路径数的上限即为 4^9=262\,144，又因为个数不大，我们可以直接暴枚所以路径。我们可以采用广搜，记录当前的坐标、已走步数、路径上每个坐标被访问的次数（这个可以用 map 来维护），依次更新全局最大值即可。

单点时间复杂度 \mathcal O(4^S\cdot S)，对于 S\le9 轻松过。

Code

#include"bits/stdc++.h"
using namespace std;
const int N = 25;
int t, r, c, x, y, s;
int d[][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
double p, q;
bool has[N][N];//格子类型
double ans;
struct node {
    int x, y, sum;//sum 记录步数
    map<pair<int, int>, int>cnt;
};
double count(map<pair<int, int>, int> &cnt) {
    double re = 0;
    for (auto [pos, t] : cnt) {
        if (has[pos.first][pos.second])
            re += 1 - pow(1 - p, t);
        else
            re += 1 - pow(1 - q, t);
    }
    return re;
}
void bfs() {
    queue<node> q;
    q.push({x, y, 0, map<pair<int, int>, int>()});
    while (q.size()) {
        node cur = q.front();
        q.pop();
        if (cur.sum == s) {
            ans = max(ans, count(cur.cnt));
            continue;
        }
        for (int i = 0; i < 4; i++) {
            int tx = cur.x + d[i][0], ty = cur.y + d[i][1];
            if (tx < 1 || tx > r || ty < 1 || ty > c)
                continue;
            node nxt = cur;
            nxt.x = tx, nxt.y = ty, nxt.sum++;
            nxt.cnt[{tx, ty}]++;
            q.push(nxt);
        }
    }
}
signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> t;
    for (int ca = 1; ca <= t; ca++) {
        cin >> r >> c >> x >> y >> s >> p >> q;
        x++, y++;//转化为 1-based
        for (int i = 1; i <= r; i++) 
            for (int j = 1; j <= c; j++) {
                char ch;
                cin >> ch;
                has[i][j] = (ch == 'A');
            }
        ans = 0;//注意多测清空
        bfs();
        printf("Case #%d: %.7lf\n", ca, ans);
    }
    return 0;
}