概率dp-九度-1546-迷宫问题
题目链接：
http://ac.jobdu.com/problem.php?pid=1546
题目意思：
有一个起点S，多个出口E，#代表不能走，每次等概率的随机选择下一个可以行走的位置，求从S到出口的期望。
解题思路：
高斯消元求解期望。
先BFS预处理能够到达的出口的位置，然后如果从起点不能到达终点，直接输出-1.
然后对于无效的点，置该未知数的解为-1，否则依据dp[i][j]=1+dp[i-1][j]*1/4+dp[i][j+1]*1/4+dp[i+1][j]*1/4+dp[i][j-1]*1/4,构建n*m个方程，注意有些位置的可行位置数小于4，为cnt的话，此时的下一步概率为1/cnt.
然后解方程，求出唯一解。
PS:
解方程时，如果有的未知数有解，有的无解，可以将无解的情况置一个特殊值，然后按有唯一解的方式来解方程，避免无解未知数对有解未知数的影响。
方程系数要清零。wa了好几次。
代码：
#include<iostream>#include<cmath>#include<cstdio>#include<sstream>#include<cstdlib>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<ctime>#include<bitset>#define eps 1e-8#define INF 0x3f3f3f3f#define PI acos(-1.0)#define ll __int64#define LL long long#define lson l,m,(rt<<1)#define rson m+1,r,(rt<<1)|1#define M 1000000007#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;#define Maxn 20char sa[Maxn][Maxn];int n,m,num,dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};double dp[Maxn][Maxn],pp[Maxn][Maxn];double g[Maxn*Maxn][Maxn*Maxn],ans[Maxn*Maxn];bool vis[Maxn][Maxn];void gaosi(int r,int c){ for(int i=0,j=0;i<r&&j<c;i++,j++) { int t=i; for(int p=i+1;p<=r;p++) if(fabs(g[p][j])>fabs(g[t][j])) t=p; if(fabs(g[t][j])<eps) //这是多解的情况 continue; if(t-i) //不相同，则交换 { for(int p=j;p<=c;p++) swap(g[t][p],g[i][p]); } for(int p=i+1;p<=r;p++) { double tmp=g[p][j]/g[i][j]; if(fabs(tmp)<eps) continue; g[p][j]=0.0; for(int q=j+1;q<=c;q++) g[p][q]-=tmp*g[i][q]; } } for(int p=r;p>=0;p--) { if(fabs(g[p][p])<eps) //无解的情况 continue; ans[p]=g[p][c]; for(int q=r;q>p;q--) ans[p]-=g[p][q]*ans[q]; ans[p]/=g[p][p]; }}bool iscan(int x,int y){ if(x<0||x>=n||y<0||y>=m) return false; return true;}int sx,sy;bool bfs() //从S出发找到所有可行的位置{ bool flag=false; queue<pair<int,int> >myq; myq.push(make_pair(sx,sy)); memset(vis,false,sizeof(vis)); vis[sx][sy]=true; while(!myq.empty()) { int x=myq.front().first; int y=myq.front().second; myq.pop(); for(int i=0;i<4;i++) { int ans=x+dir[i][0],yy=y+dir[i][1]; if(!iscan(ans,yy)||vis[ans][yy]||sa[ans][yy]=='#') continue; vis[ans][yy]=true; myq.push(make_pair(ans,yy)); if(sa[ans][yy]=='E') //能够到达终点 flag=true; } } return flag;}double dl(double a){ if(fabs(a)<eps) return 0; return a;}int main(){ while(~scanf("%d%d",&n,&m)) { int ss; for(int i=0;i<n;i++) { scanf("%s",sa[i]); for(int j=0;j<m;j++) { if(sa[i][j]=='S') { sx=i,sy=j; ss=i*m+j; } } } if(!bfs()) //不能够到达终点 { printf("-1\n"); continue; } num=-1; int last=n*m; memset(g,0,sizeof(g)); for(int i=0;i<n;i++) for(int j=0;j<m;j++) { num++; int tmp=i*m+j; if(!vis[i][j]) //无解的位置 { g[num][tmp]=1; g[num][last]=-1; } else { if(sa[i][j]=='E') //终点位置 { g[num][tmp]=1; g[num][last]=0; continue; } int cnt=0,next[5]; for(int k=0;k<4;k++) //求出下一步可行的位置数 { int x=i+dir[k][0],y=j+dir[k][1]; if(iscan(x,y)&&sa[x][y]!='#'&&vis[x][y]) { cnt++; next[cnt]=x*m+y; } } g[num][tmp]=1; g[num][last]=1; for(int k=1;k<=cnt;k++) //构建当前位置的方程 g[num][next[k]]=-1.0/(cnt*1.0); } } gaosi(n*m-1,n*m); ans[ss]=dl(ans[ss]); if(ans[ss]>0) printf("%.2f\n",ans[ss]); else printf("-1\n"); } return 0;}