HDU2262 Where is the canteen 數學期望 高斯消元

HDU2262 Where is the canteen

題目連結：[http://acm.hdu.edu.cn/showproblem.php?pid=2262]

Time Limit: 10000/5000 MS (Java/Others)	Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2364	Accepted Submission(s): 772

Problem Description

After a long drastic struggle with himself, LL decide to go for some snack at last. But when steping out of the dormitory, he found a serious problem : he can’t remember where is the canteen… Even worse is the campus is very dark at night. So, each time he move, he check front, back, left and right to see which of those four adjacent squares are free, and randomly walk to one of the free squares until landing on a canteen.

Input

Each case begin with two integers n and m ( n<=15,m<=15 ), which indicate the size of the campus. Then n line follow, each contain m characters to describe the map. There are 4 different type of area in the map:

‘@’ is the start location. There is exactly one in each case.

‘#’ is an impassible square.

‘$’ is a canteen. There may be more than one in the campus.

‘.’ is a free square.

Output

Output the expected number of moves required to reach a canteen, which accurate to 6 fractional digits. If it is impossible , output -1.

題目大意：

LL在一個 n * m 的學校裡，現在從宿舍出發，每次随機向四個方向中可以移動的一個方向移動一個機關，問到達食堂需要的步數的數學期望是多少（學校裡有多個食堂），如果到達不了輸出-1

’ @ ’ 表示宿舍

’ # ’ 表示障礙物

’ $ ’ 表示食堂

’ . ’ 表示空地

分析：

DP[ i ]表示 i 點到食堂的步數的數學期望值

不難得出機率DP的狀态轉移方程：

D P [ i ] = D P [ j 1 ] + ⋯ + D P [ j t ] t + 1 DP[i]=\frac {DP[j_1]+\cdots+DP[j_t]}t+1 DP[i]=tDP[j1​]+⋯+DP[jt​]​+1

其中j1、……jt為可以從 i 直接到達的點，并且如果 j 點是食堂的話DP[ j ] = 0

将上述狀态轉移方程形式改變一下變成線性方程：

t ⋅ D P [ i ] − D P [ j 1 ] − ⋯ − D P [ j t ] = t t\cdot DP[i]-DP[j_1]-\cdots-DP[j_t]=t t⋅DP[i]−DP[j1​]−⋯−DP[jt​]=t

是以首先用BFS找出連通圖，也就是可以到達的所有點

對于每一個可以到達的點都可以得到一個線性方程

組合在一起得到一個線性方程組

用高斯消元對線性方程組進行處理就可以得到答案了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
static const int maxn = 20;
static const int MAXN = 400;
static const int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int n,m,sx,sy,tn;
char mp[maxn][maxn];        //記錄campus的圖
int d[MAXN];                //可以走的方向數
int dmap[MAXN];             //可行點位置标号對應的序号
double gauss[MAXN][MAXN];   //矩陣 用于消元
vector<int> v[MAXN];        //下一步可以走到的位置
int pos(int x,int y){
    int pos = (x-1)*m+y;
    return pos;
}
//pos用于算出位置标号
bool bfs(){
    tn = 0;									//可行點總數
    bool ok = false;                        //判斷是否能走到食堂
    int used[maxn][maxn];                   //bfs标記
    memset(used,0,sizeof(used));
    for(int i=0;i<MAXN;i++) v[i].clear();
    queue<pair<int,int> > q;
    used[sx][sy] = 1;
    q.push(make_pair(sx,sy));
    while(!q.empty()){
        int nowx = q.front().first;
        int nowy = q.front().second;
        dmap[pos(nowx,nowy)] = ++tn;        //記錄可行點位置序号
        int tmpd = 0;                       //可走的方向數
        q.pop();
        for(int i=0;i<4;i++){
            int nextx = nowx + dir[i][0];
            int nexty = nowy + dir[i][1];
            if(nextx<=n&&nextx>=1&&nexty<=m&&nexty>=1){
                if(mp[nextx][nexty]=='.'){
                    v[dmap[pos(nowx,nowy)]].push_back(pos(nextx,nexty));
                    tmpd++;
                    if(!used[nextx][nexty]){
                        q.push(make_pair(nextx,nexty));
                        used[nextx][nexty] = 1;
                    }
                }
                else if(mp[nextx][nexty]=='$'){
                    ok = true;
                    tmpd++;
                }
            }
        }
        d[dmap[pos(nowx,nowy)]] = tmpd;
    }
    return ok;
}
int main(){
    while(scanf("%d %d",&n,&m)!=EOF){
        memset(d,0,sizeof(d));
        memset(gauss,0,sizeof(gauss));
        for(int i=1;i<=n;i++){
            getchar();
            for(int j=1;j<=m;j++){
                mp[i][j] = getchar();
                if(mp[i][j]=='@'){
                    sx = i;
                    sy = j;
                    mp[i][j] = '.';
                }
            }
        }
        if(!bfs()){
            printf("-1\n");
            continue;
        }

        //gauss_jordan:
        for(int i=1;i<=tn;i++){
            gauss[i][i] = d[i];
            for(int j=0;j<v[i].size();j++){
                gauss[i][dmap[v[i][j]]] = -1;
            }
            gauss[i][tn+1] = d[i];
        }
        for(int i=1;i<tn;i++){
            for(int j=i+1;j<=tn;j++){
                double k = gauss[j][i]/gauss[i][i];
                for(int t=i;t<=tn+1;t++){
                    gauss[j][t] -= k * gauss[i][t];
                }
            }
        }
        bool ok = false;
        for(int i=tn;i>1;i--){
            if(gauss[i][i]==0){
                ok = true;
                printf("-1\n");
                break;
            }
            for(int j=i-1;j>=1;j--){
                double k = gauss[j][i]/gauss[i][i];
                gauss[j][i] = 0;
                gauss[j][tn+1] -= k * gauss[i][tn+1];
            }
        }
        if(ok) continue;
        printf("%.6f\n",gauss[dmap[pos(sx,sy)]][tn+1]/gauss[dmap[pos(sx,sy)]][dmap[pos(sx,sy)]]);
    }
    return 0;
}