首页 > 代码库 > 九度oj 题目1546:迷宫问题 (概率dp guess消元)
九度oj 题目1546:迷宫问题 (概率dp guess消元)
给定一个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 <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <string> #include <map> #include <stack> #include <vector> #include <set> #include <queue> #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; k<equ&&col<var; k++,col++) { max_r=k; for(i=k+1; i<equ; i++) if(fabs(a[i][col])>fabs(a[max_r][col])) max_r=i; if(fabs(a[max_r][col])<eps)return 0; if(k!=max_r) { for(j=col; j<var; j++) swap(a[k][j],a[max_r][j]); swap(x[k],x[max_r]); } x[k]/=a[k][col]; for(j=col+1; j<var; j++)a[k][j]/=a[k][col]; a[k][col]=1; for(i=0; i<equ; i++) if(i!=k) { x[i]-=x[k]*a[i][k]; for(j=col+1; j<var; j++)a[i][j]-=a[k][j]*a[i][col]; a[i][col]=0; } } return 1; } bool isok(int x,int y) { if(x<1||x>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; queue<node>q; 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 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。