当前位置:编程学习 > C/C++ >>

ZJUT 1423 地下迷宫(期望DP&高斯消元)

地下迷宫 
Time Limit:1000MS  Memory Limit:32768K
Description:
由于山体滑坡,DK被困在了地下易做图王国迷宫。为了抢在DH之前来到TFT,DK必须尽快走出此迷宫。此迷宫仅有一个出口,而由于大BOSS的力量减弱影响到了DK,使DK的记忆力严重下降,他甚至无法记得他上一步做了什么。所以他只能每次等概率随机的选取一个方向走。当然他不会选取周围有障碍的地方走。如DK周围只有两处空地,则每个都有1/2的概率。现在要求他平均要走多少步可以走出此迷宫。
Input:
先是一行两个整数N, M(1<=N, M<=10)表示迷宫为N*M大小,然后是N行,每行M个字符,'.'表示是空地,'E’表示出口,'D’表示DK,'X’表示障碍。
Output:
如果DK无法走出或要超过1000000步才能走出,输出tragedy!,否则输出一个实数表示平均情况下DK要走几步可以走出迷宫,四舍五入到小数点后两位。
Sample Input:
1 2
ED
3 3
D.X
.X.
X.E
Sample Output:
1.00
tragedy!
Source:
DK 
思路:
首先对地图节点重新标号。假设E[i]表示DK从i点开始走出迷宫的期望值。
那么E[i]=(E[a1]+E[a2]+E[a3]+...+E[an])/n+1,其中a1...an是i的相邻节点。
那么对于每一个DK可达的节点来说,都可以为它建立这样的一个方程。现
在假设DK可达的点有N个,那么我们最终将会得到N元一次方程组。方程成
环所以利用高斯消元解出E[No[S]]。其中S是DK的起点,No[S]是重标号后的
起点这里要重点注意的是,我们联立方程的时候,一定要注意DK可达这个条
件,不然就会导致无解的情况。貌似zjutoj崩了。不能交题了。代码仅供参考。
详细见代码:
 
#include <iostream>  
#include<stdio.h>  
#include<math.h>  
#include<string.h>  
#include<queue>  
using namespace std;  
const int maxn=15;  
const double eps=1e-9;  
char maze[maxn][maxn];//记录地图  
int pp[maxn][maxn];//重编号  
int dx[4]={0,0,-1,1};  
int dy[4]={1,-1,0,0};  
double mat[maxn][maxn];//记录矩阵  
int n,m,cnt,ptr;  
struct node  
{  
    int x,y;  
    node(int xx,int yy)  
    {  
        x=xx;  
        y=yy;  
    }  
    node(){}  
} st,ed,t;  
queue<node> q;  
  
bool isok(int x,int y)//判断是否越界  
{  
    return x>=0&&x<n&&y>=0&&y>=0&&y<m&&maze[x][y]!='X';  
}  
void bfs()//宽搜。记录可到达点  
{  
    int nx,ny,i;  
    while(!q.empty())  
        q.pop();  
    cnt=0;  
    nx=st.x;  
    ny=st.y;  
    pp[nx][ny]=cnt++;  
    q.push(st);  
    while(!q.empty())  
    {  
        t=q.front();  
        q.pop();  
        for(i=0;i<4;i++)  
        {  
            nx=t.x+dx[i];  
            ny=t.y+dy[i];  
            if(isok(nx,ny)&&pp[nx][ny]==-1)  
            {  
                q.push(node(nx,ny));  
                pp[nx][ny]=cnt++;//对可到达点编号  
            }  
        }  
    }  
}  
bool guass()//高斯消元  
{  
    int row,i,j,id;  
    double maxx,var;  
    for(row=0;row<cnt;row++)//遍历行。重点在mat[row][row]先找此处最大系数。然后把以下方程的对应未知数消去  
    {  
        maxx=fabs(mat[row][row]);  
        id=row;//id记录位置  
        for(i=row+1;i<cnt;i++)  
        {  
            if(fabs(mat[i][row])>maxx)  
            {  
                maxx=fabs(mat[i][row]);//注意是绝对值大  
                id=i;  
            }  
        }  
        if(maxx<eps)  
            return false;  
        if(id!=row)//如果就是当前处理行就不用交换  
        {  
            for(i=row;i<=cnt;i++)//交换最大行和当前行  
                swap(mat[row][i],mat[id][i]);  
        }  
        for(i=row+1;i<cnt;i++)//遍历行。所以<cnt.把当前处理行以下的mat[row][row]变量消去。  
        {  
            if(fabs(mat[i][row])<eps)//本来就为0就不用处理了  
                continue;  
            var=mat[i][row]/mat[row][row];  
            for(j=row;j<=cnt;j++)//包括扩展矩阵所以c<=cnt。  
                mat[i][j]-=mat[row][j]*var;  
        }  
    }  
    for(i=cnt-1;i>=0;i--)//从最后一个系数开始  
    {  
        for(j=i+1;j<cnt;j++)  
            mat[i][cnt]-=mat[i][j]*mat[j][j];  
        mat[i][i]=mat[i][cnt]/mat[i][i];//现在系数矩阵的对角线用于记录答案。  
    }  
    return true;  
}  
int main()  
{  
    int i,j,k,nx,ny,p;  
  
    while(~scanf("%d%d",&n,&m))  
    {  
        for(i=0;i<n;i++)  
        {  
            scanf("%s",maze[i]);  
            for(j=0;j<m;j++)  
            {  
                if(maze[i][j]=='D')  
                    st.x=i,st.y=j;  
                else if(maze[i][j]=='E')  
                    ed.x=i,ed.y=j;  
            }  
        }  
        memset(pp,-1,sizeof pp);  
        bfs();  
        if(pp[ed.x][ed.y]==-1)  
        {  
            printf("tragedy!\n");  
            continue;  
        }  
        memset(mat,0,sizeof mat);  
        for(i=0;i<n;i++)  
        {  
            for(j=0;j<m;j++)  
            {  
                if(pp[i][j]!=-1)//以每个可到达点建立方程组  
                {  
                    ptr=0;  
                    p=pp[i][j];  
                    for(k=0;k<4;k++)  
                    {  
                        nx=i+dx[k];  
                        ny=j+dy[k];  
                        if(isok(nx,ny))  
                        {  
                            mat[p][pp[nx][ny]]=-1;  
                            ptr++;  
                        }  
                    }  
                    mat[p][p]=ptr;  
                    mat[p][cnt]=ptr;  
                }  
            }  
        }  
        p=pp[ed.x][ed.y];  
        memset(mat[p],0,sizeof mat[p]);  
        mat[p][p]=1;//在终点步数的期望为0.  
        if(guass())  
        {  
            p=pp[st.x][st.y];  
            if(mat[p][p]<=1000000)  
                printf("%.2lf\n",mat[p][p]);  
            else  
                printf("tragedy!\n");  
        }  
        else  
            printf("tragedy!\n");  
    }  
    return 0;  
}  

 

 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,