概率dp-九度-1546-迷宫问题 - c++编程基础

题目意思：

有一个起点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  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#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 20  
  
char 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;ifabs(g[t][j]))  
                t=p;  
        if(fabs(g[t][j])=0;p--)  
    {  
        if(fabs(g[p][p])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




 >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)0)  
            printf("%.2f\n",ans[ss]);  
        else  
            printf("-1\n");  
    }  
   return 0;  
}