九度oj 题目1546：迷宫问题（概率dp guess消元）

题目链接：点击打开链接

题目描述：

给定一个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 
              
               
#include 
               
                 #include 
                
                  #include 
                 
                   #include 
                  
                    #include 
                   
                     #include 
                     #include 
                     
                       #include 
                      
                        #include 
                       
                         #include 
                        
                          #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
                         
                          fabs(a[max_r][col])) max_r=i; if(fabs(a[max_r][col])
                          
                           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
                           
                            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 */