程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 九度oj 題目1546：迷宮問題（概率dp guess消元）

九度oj 題目1546：迷宮問題（概率dp guess消元）

編輯：C++入門知識

題目鏈接：點擊打開鏈接

題目描述：

給定一個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; kfabs(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;
    queueq;
    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
*/