这个模型跟小时候玩的大富翁棋类游戏差不多，起点是0，终点是N，每次掷骰子走1~6步，格子分为3种，前进1~6格，后退1~6格，以及停止一回合，求到达终点所需回合数的期望。
用E(I)表示从第I个格子走到终点所需回合的期望，E(N)=0，转移方程为 E(I)=sum(1/6*(E(K1)+1))+sum(1/6*(E(K2)+2))。K1,K2都是从I掷1~6能走到的格子，如果这个格子有操作，就要跳到操作后的格子，第一个sum里求的是不会停一回合的期望和，第二个sum里求的是走到停一回合格子的期望和。
因为有后退操作，所以转移是有环的，不能用记忆化搜索，要用高斯消元来做。
一开始可以DFS一遍标记所以能到达的格子，这样可以直接判断是否有解。对于不可达的点，也不需要去消元。
比较蛋疼的是遇到端点折回的情况，比如在N=2时，在1掷了个5，那路线就是1->2->1->0->1->2。。没总结出用什么式子算，索性写了个暴力模拟一直调整直到到达0~N的范围中。。
这题精度比较低，暴力的循环DP1000次貌似也能过。。我本机随机数据测了一下，暴力DP的精度还是有限的，2位的精度基本都对上了，但位数再高一点精度就差不少了，所以这类题最好还是高斯消元解吧，反正也不麻烦。
1 #include <stdio.h>
2 #include <string.h>
3 #include <math.h>
4 #include <algorithm>
5 #define MAXN 105
6 #define INF 0x3f3f3f3f
7 #define eps 1e-9
8 using namespace std;
9 int n, nf, tx, ty;
10 int reach[MAXN], fp[MAXN], id[MAXN], ids;
11 double x[MAXN][MAXN], ans[MAXN];
12 double gauss(int n,int m) {
13 int row = 0, col = 0;
14 for (;row < n && col < m; col++) {
15 int maxr = row;
16 for (int i = row+1; i < n; i++)
17 if (fabs(x[i][col]) > fabs(x[maxr][col]))maxr = i;
18 if (fabs(x[maxr][col]) < eps) continue;
19 if (maxr != row) for (int i = 0; i <= m; i++) swap(x[row][i], x[maxr][i]);
20 for (int k1 = row+1; k1 < n; k1++) {
21 double div = x[k1][col] / x[row][col];
22 for (int k2 = col; k2 <= m; k2++) {
23 x[k1][k2] -= div * x[row][k2];
24 }
25 }
26 row++;
27 }
28 memset(ans, 0, sizeof ans);
29 for (int i = n-1; i >= 0; i--) {
30 double tmp = 0;
31 for (int j = i+1; j < m; j++)
32 tmp += ans[j] * x[i][j];
33 ans[i] = (- x[i][m] - tmp) / x[i][i];
34 }
35 return ans[0];
36 }
37 int getnp(int p,int i) {
38 int np = i+p;
39 while (np < 0 || np > n) np = np > n ? 2*n-np : -np;
40 return np;
41 }
42 void dfsreach(int p) {
43 reach[p] = 1;
44 for (int i = 1;i <= 6; i++) {
45 int np = getnp(p, i);
46 if (fp[np] != INF) np = getnp(np, fp[np]);
47 if (!reach[np]) dfsreach(np);
48 }
49 }
50 void solve() {
51 memset(reach, 0 ,sizeof reach);
52 dfsreach(0);
53 if (reach[n] == 0) {
54 printf("Impossible\n");
55 return;
56 }
57 ids = 0;
58 double one = 1.0/6.0;
59 for (int i = 0; i < n; i++) if (reach[i]) id[i] = ids++;
60 memset(x, 0, sizeof x);
61 for (int p = 0; p < n; p++) {
62 if (reach[p] == 0) continue;
63 x[id[p]][id[p]] = -1;
64 for (int i = 1; i <= 6; i++) {
65 int np = getnp(p, i), nfp = fp[np];
66 if (fp[np] != INF) np = getnp(np, fp[np]);
67 //已经到达终点
68 if (np == n) {
69 x[id[p]][ids] += one;
70 //注意,是第一步跳到了停止上才是停止
71 } else if(nfp == 0) {
72 x[id[p]][id[np]] += one;
73 x[id[p]][ids] += one * 2;
74 } else {
75 x[id[p]][id[np]] += one;
76 x[id[p]][ids] += one;
77 }
78 }
79 }
80 double x = gauss(ids, ids);
81 printf("%.2f\n", x);
82 }
83 int main(){
84 freopen("test.in","r",stdin);
85 freopen("test.out","w",stdout);
86 while (scanf("%d", &n) != EOF) {
87 scanf("%d", &nf);
88 memset(fp, 0x3f, sizeof fp);
89 for (int i = 0; i < nf; i++)
90 scanf("%d%d", &tx, &ty), fp[tx] = ty;
91 scanf("%d", &nf);
92 for (int i = 0; i < nf; i++)
93 scanf("%d%d", &tx, &ty), fp[tx] = -ty;
94 scanf("%d", &nf);
95 for (int i = 0; i < nf; i++)
96 scanf("%d", &tx), fp[tx] = 0;
97 solve();
98 }
99 return 0;
100 }