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++ ,