对于每个点两个方向(两头只有一个方向)建一个点,然后预处理出每个点走到哪个点,列出方程式高斯消元就行了。记得前面出那些点不可到,他们的期望没有意义。
方程式比较显然:
(表示点走步到的点)
#include
using namespace std;
const int MAXN = 205;
const double eps = 1e-8;
struct node {
int x, y;
node(){}
node(int x, int y):x(x), y(y){}
}b[MAXN];
double p[MAXN], a[MAXN][MAXN];
bool vis[MAXN];
inline bool gauss(int n) {
for(int j = 1; j if(!vis[j]) continue;
if(!a[j][j]) {
for(int i = j+1; i if(a[i][j]) {
for(int k = j; k swap(a[i][k], a[j][k]);
break;
}
}
if(fabs(a[j][j]) for(int i = j+1; i double v = a[i][j] / a[j][j];
for(int k = j; k a[i][k] -= v * a[j][k];
}
}
for(int i = n; i >= 1; --i) if(vis[i]) {
for(int j = i+1; j a[i][n+1] -= a[j][n+1] * a[i][j];
a[i][n+1] /= a[i][i];
}
return 1;
}
int n, m, Y, X, D, cnt, id[MAXN][2], to[MAXN][MAXN];
queueq;
inline bool bfs() {
memset(vis, 0, sizeof vis);
vis[id[X][D]] = 1;
q.push(id[X][D]);
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = 1; i if(p[i] > eps && !vis[to[u][i]])
vis[to[u][i]] = 1, q.push(to[u][i]);
}
return vis[id[Y][0]] | vis[id[Y][1]];
}
int main() {
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d%d%d%d", &n, &m, &Y, &X, &D); ++X, ++Y;
if(D == -1) D = X == 1;
else D ^= 1;
//0 -> leftwards
//1 -> rightwards
for(int i = 1; i cnt = 0;
id[1][0] = id[1][1] = ++cnt; b[cnt] = node(1, 1);
id[n][0] = id[n][1] = ++cnt; b[cnt] = node(n, 0);
for(int i = 2; i id[i][0] = ++cnt, b[cnt] = node(i, 0),
id[i][1] = ++cnt, b[cnt] = node(i, 1);
for(int i = 1; i node t = b[i];
t.x += t.y ? 1 : -1;
if(t.x == 1 || t.x == n) t.y ^= 1;
to[i][1] = id[t.x][t.y];
}
for(int j = 2; j for(int i = 1; i to[i][j] = to[to[i][j-1]][1];
if(!bfs()) puts("Impossible !");
else {
memset(a, 0, sizeof a);
for(int i = 1; i a[i][i] = 1;
if(!vis[i] || i == id[Y][0] || i == id[Y][1]) continue;
for(int j = 1; j a[i][to[i][j]] -= p[j],
a[i][cnt+1] += p[j] * j;
}
if(!gauss(cnt)) puts("Impossible !");
double ans = a[id[X][D]][cnt+1];
printf("%.2fn", ans);
}
}
}