0828-T4 聪聪与可可
题意
猫抓老鼠。
猫每次会走到四周距离老鼠最近的点。若没抓到老鼠还会再走一次。
老鼠每次会等概率向四周走一步，求猫抓到老鼠的期望时间。
思路
与处理出 \(nxt_{i,j}\) 表示猫在 \(i\) 老鼠在 \(j\)，猫下一步走到哪里。
\(f_{i,j}\) 表示猫在 \(i\) 老鼠在 \(j\)，猫抓到老鼠的期望次数。
若 \(i=j\)，\(f_{i,j} = 0\)。
若猫一步吃到老鼠，\(f_{i,j}=1\)。
\[f_{i,j}=\frac{1}{p}\sum f_{k,l} + 1 \]\(k\) 表示猫下两步走到哪里，\(l\) 表示老鼠周围的点，\(p\) 是老鼠周围的点的个数加一。
使用记忆化搜索实现。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m, nxt[N][N], d[N][N];
vector <int> e[N];
double f[N][N];
void bfs(int s) {
queue <int> q;
q.push(s);
while (!q.empty()) {
int p = q.front(); q.pop();
for (auto v : e[p]) {
if (d[s][v] || v == s) continue;
d[s][v] = d[s][p] + 1;
q.push(v);
}
}
}
double dfs(int cat, int mouse) {
if (cat == mouse) return f[cat][mouse] = 0;
int nxtcat = nxt[cat][mouse];
if (nxtcat == mouse) return f[cat][mouse] = 1;
nxtcat = nxt[nxtcat][mouse];
if (nxtcat == mouse) return f[cat][mouse] = 1;
if (f[cat][mouse]) return f[cat][mouse];
double res = 1, P = e[mouse].size() + 1;
res += dfs(nxtcat, mouse) / P;
for (auto nxtmouse : e[mouse])
res += dfs(nxtcat, nxtmouse) / P;
return f[cat][mouse] = res;
}
int main() {
cin >> n >> m;
int C, M; cin >> C >> M;
for (int i = 1, u, v; i <= m; i ++) {
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
for (int i = 1; i <= n; i ++) bfs(i);
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
d[0][j] = 1e9; int& p = nxt[i][j];
for (auto v : e[i]) {
if (d[v][j] < d[p][j]) p = v;
if (d[v][j] == d[p][j] && v < p) p = v;
}
}
}
dfs(C, M);
cout << fixed << setprecision(3) << f[C][M] << "\n";
return 0;
}