题目链接：点击打开链接
题目描述：
给定一个n*m的迷宫，如
S..
..#
E.E
其中，S代表开始位置，#代表不可行走的墙，E代表出口。
主人公从开始位置出发，每次等概率的随机选择下一个可以行走的位置，直到到达某一个出口为止。
现在他想知道，在这一概率事件中，它从开始位置走到某一个出口的期望步数是多少。
输入包含多组测试用例，每组测试用例由两个整数n，m(1<=n,m<=15)开始，代表迷宫的大小
接下去n行每行m个字符描述迷宫信息，具体规则如题面所述。
数据保证至少存在一个E和一个S，但可能存在多个E。
输出一个浮点数，表示他走出迷宫的期望步数，保留两位小数。若主人公不可能走出迷宫，输出-1。
1 2 SE 2 2 S. .E 1 3 S#E
1.00 4.00 -1
走到.之后会有几率往回走。
题意：
有一个起点S，多个出口E，#代表不能走，每次等概率的随机选择下一个可以行走的位置，求从S到出口的期望。
思路：
先bfs预处理能到达的点，不能到达终点则输出-1，否则dp。
dp[i]-到达i点后要到达终点需要的步数的期望。
对每一个能到达的点x0，假设其相邻的能到达的点有x1、x2、x3.
则dp[x0]=1+dp[x1]/3+dp[x2]/3+dp[x3];
ps：注意可能有多个终点，终点的期望都为0.
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 405
#define MAXN 100005
#define OO (1LL<<35)-1
#define mod 1000000009
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;
int n,m,sx,sy,flag,cnt;
double a[maxn][maxn],x[maxn];
//方程的左边的矩阵和等式右边的值，求解之后x存的就是结果 下标从0开始
int equ,var;//方程数和未知数个数
char mp[25][25];
int vis[25][25];
int dx[]= {-1,1,0,0};
int dy[]= {0,0,-1,1};
struct node
{
int x,y;
} cur,now;
int Gauss()
{
int i,j,k,col,max_r;
for(k=0,col=0; k<equ&&col<var; k++,col++)
{
max_r=k;
for(i=k+1; i<equ; i++)
if(fabs(a[i][col])>fabs(a[max_r][col]))
max_r=i;
if(fabs(a[max_r][col])<eps)return 0;
if(k!=max_r)
{
for(j=col; j<var; j++)
swap(a[k][j],a[max_r][j]);
swap(x[k],x[max_r]);
}
x[k]/=a[k][col];
for(j=col+1; j<var; j++)a[k][j]/=a[k][col];
a[k][col]=1;
for(i=0; i<equ; i++)
if(i!=k)
{
x[i]-=x[k]*a[i][k];
for(j=col+1; j<var; j++)a[i][j]-=a[k][j]*a[i][col];
a[i][col]=0;
}
}
return 1;
}
bool isok(int x,int y)
{
if(x<1||x>n||y<1||y>m) return false ;
return true ;
}
void bfs()
{
int i,j,t,tx,ty;
flag=0;
memset(vis,-1,sizeof(vis));
cnt=-1;
vis[sx][sy]=++cnt;
queue<node>q;
cur.x=sx, cur.y=sy;
q.push(cur);
while(!q.empty())
{
now=q.front();
if(mp[now.x][now.y]==‘E‘) flag=1;
q.pop();
for(i=0; i<4; i++)
{
tx=now.x+dx[i];
ty=now.y+dy[i];
if(isok(tx,ty)&&mp[tx][ty]!=‘#‘&&vis[tx][ty]==-1)
{
cur.x=tx;
cur.y=ty;
vis[tx][ty]=++cnt;
q.push(cur);
}
}
}
}
void solve()
{
int i,j,k,t,tx,ty,ha,cxx;
equ=var=cnt+1;
memset(a,0,sizeof(a)); // 记得初始化
memset(x,0,sizeof(x));
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
if(vis[i][j]==-1) continue ;
ha=vis[i][j];
if(mp[i][j]==‘E‘) // 终点的期望为0
{
a[ha][ha]=1;
x[ha]=0;
continue ;
}
cxx=0;
for(k=0; k<4; k++)
{
tx=i+dx[k];
ty=j+dy[k];
if(isok(tx,ty)&&vis[tx][ty]!=-1)
{
cxx++;
a[ha][vis[tx][ty]]=-1;
}
}
a[ha][ha]=cxx;
x[ha]=cxx;
}
}
Gauss();
printf("%.2f\n",x[vis[sx][sy]]);
}
int main()
{
int i,j,t;
while(~scanf("%d%d",&n,&m))
{
for(i=1; i<=n; i++)
{
scanf("%s",mp[i]+1);
for(j=1; j<=m; j++)
{
if(mp[i][j]==‘S‘) sx=i,sy=j;
}
}
bfs();
if(!flag) printf("-1\n");
else
{
solve();
}
}
return 0;
}
/*
1 2
SE
2 2
S.
.E
1 3
S#E
*/
九度oj 题目1546：迷宫问题 （概率dp guess消元）,布布扣,bubuko.com
九度oj 题目1546：迷宫问题 （概率dp guess消元）
原文：http://blog.csdn.net/tobewhatyouwanttobe/article/details/26098541