HDU 2262 Where is the canteen(高斯求期望问题)
转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
题目：有一个地图，一个人从某个点出发，问走到花园的期望步数为多少
http://acm.hdu.edu.cn/showproblem.php?pid=2262
基础的高斯求概率。
设某点的期望步数为Ei。
那么目标的Ei=0。
Ei=(Enext1+Enext2……Enextk)/k+1。
整理下就是Enext1+Enext2……Enextk-k*Ei=-k
根据i点的后继结点nextj，那么从所有的后继结点走一步都可以到达i点。便是所有后继的期望平均值+1.
以此建立方程组，然后用高斯消元求解。
以下几个地方需要注意：
1、后继必须是可达目标的，这一点可以在搜索得到，所有的可达点，不是可达的不能计入
2、这题有多个出口，在搜索的时候需要注意，可以dfs,bfs,floodfill
3、让我纠结的高斯，我写的太shi了，而且没有通用性。注意精度
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<vector>#include<cmath>#define LL long long#define MOD 1000000007#define eps 1e-6#define zero(a) fabs(a)<epsusing namespace std;int n,m;int way[4][2]={0,1,0,-1,1,0,-1,0};char str[20][20];double a[230][230];bool flag[20][20];int ans;//搜索预处理一下bool bfs(){ int s,e; memset(flag,false,sizeof(flag)); queue<int>x,y; while(!x.empty()) x.pop(); while(!y.empty()) y.pop(); for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(str[i][j]=='$'){ x.push(i); y.push(j); s=i; e=j; flag[i][j]=true; } while(!x.empty()){ int ux=x.front(),uy=y.front(),vx,vy; x.pop();y.pop(); for(int i=0;i<4;i++){ vx=ux+way[i][0]; vy=uy+way[i][1]; if(vx>=0&&vx<n&&vy>=0&&vy<m&&str[vx][vy]!='#'&&!flag[vx][vy]){ flag[vx][vy]=true; x.push(vx);y.push(vy); } } } return false;}//高斯，写得太shi了bool gauss(int n){ int i,j; for(i=0,j=0;i<n&&j<n;j++){ int k; for(k=i;k<n;k++) if(!zero(a[k][j])) break; if(k<n){ if(i!=k) for(int r=j;r<=n;r++) swap(a[i][r],a[k][r]); if(idx==k) idx=i; double tt=1/a[i][j]; for(int r=j;r<=n;r++) a[i][r]*=tt; for(int r=0;r<n;r++) if(r!=i){ for(int t=n;t>=j;t--) a[r][t]-=a[r][j]*a[i][t]; } i++; } } for(int r=i;r<n;r++) if(!zero(a[r][n])) return false; return true;}int main(){ while(scanf("%d%d",&n,&m)!=EOF){ for(int i=0;i<n;i++) scanf("%s",str[i]); for(int i=0;i<=n*m;i++) for(int j=0;j<=n*m;j++) a[i][j]=0; bfs(); int s,e; for(int i=0;i<n;i++) for(int j=0;j<m;j++){ int cnt=0; if(str[i][j]=='@'){ s=i; e=j; } //目标的方程便是e[i]=0; if(str[i][j]=='$'){ a[i*m+j][n*m]=0; a[i*m+j][i*m+j]=1; continue; } //不可达的点可以忽略 if(str[i][j]=='#') continue; for(int k=0;k<4;k++){ int x=i+way[k][0]; int y=j+way[k][1]; if(x>=0&&x<n&&y>=0&&y<m&&str[x][y]!='#'&&flag[x][y]){ a[i*m+j][x*m+y]=1; cnt++; } } a[i*m+j][n*m]=-1*cnt; a[i*m+j][i*m+j]=-1*cnt; } if(flag[s][e]&&gauss(n*m)){ for(int i=0;i<n*m;i++) if(zero(a[i][s*m+e]-1)){ printf("%.6f\n",a[i][n*m]); break; } } else puts("-1"); } return 0;}