题目链接: http://xcacm.hfut.edu.cn/oj/problem.php?id=1168
题目大意：D是起点，E是终点。每次等概率往某个方向走，问到达终点的期望步数。到不了终点或步数超限输出tragedy!
解题思路：
如果某个点四周都不是障碍，不难有方程：
E（X,Y）= （1/4）E（X-1,Y）+ （1/4）E（X+1,Y）+ （1/4）E（X,Y-1）+ （1/4）E（X,Y+1）+1
变形为一般式，且系数化1：4*E（X,Y）-E（X-1,Y）- E（X+1,Y） - E（X,Y-1） - E（X,Y+1） = 4
更一般化，如果周围有cnt个点可去： cnt*E（X,Y）-E（X-1,Y）- E（X+1,Y） - E（X,Y-1） - E（X,Y+1） = cnt
对于不可达点（不一定是障碍）或终点：E（X,Y）= 0，这一步的处理很重要，不然会导致出现*变元，导致无穷解。
那么本题思路很明显了：
①BFS或是DFS，标记各点的可达情况。
②对于每个点（元），首先看其是否为不可达点或是终点，令其系数为1后continue
如果不是，枚举四个方向，系数设为-1。最后该点系数为cnt，解向量初始化为cnt。
③高斯消元（本模板是高斯—约当消元法）。
④由于方程是把起点和终点逆过来列方程的，所以元[起点]的解才是最后的ans。（类似记忆化搜索的方式)
#include "cstdio"
#include "queue"
#include "cstring"
#include "algorithm"
#include "math.h"
using namespace std;
#define eps 1e-15
char map[][],s[];
int n,m,T,sx,sy,ex,ey,vis[][],dir[][]={-,,,,,-,,},equ;
double ratio[][];
struct status
{
int x,y;
status(int x,int y):x(x),y(y) {}
};
void Bfs(int x,int y)
{
queue<status> Q;Q.push(status(x,y));
vis[x][y]=;
while(!Q.empty())
{
status t=Q.front();Q.pop();
for(int s=;s<;s++)
{
int X=t.x+dir[s][],Y=t.y+dir[s][];
if(X<||Y<||X>=n||Y>=m||vis[X][Y]||map[X][Y]=='X') continue;
vis[X][Y]=;
Q.push(status(X,Y));
}
}
}
void Reset()
{
for(int i=;i<n;i++)
for(int j=;j<m;j++)
{
if((i==ex&&j==ey)||!vis[i][j]) {ratio[i*m+j][i*m+j]=;continue;}
int cnt=;
for(int s=;s<;s++)
{
int x=i+dir[s][],y=j+dir[s][];
if(x>=&&y>=&&x<n&&y<m&&map[x][y]=='.')
{
ratio[i*m+j][x*m+y]=-;
cnt++;
}
}
ratio[i*m+j][equ]=ratio[i*m+j][i*m+j]=cnt;
}
}
bool Gauss()
{
for(int i=;i<equ;i++)
{
int k=i;
for(int j=i;j<equ;j++)
if(fabs(ratio[j][i])>fabs(ratio[k][i])) k=j;
swap(ratio[k],ratio[i]);
if(fabs(ratio[i][i])<eps) return false;
for(int j=i+;j<=equ;j++) ratio[i][j]/=ratio[i][i];
for(int j=;j<equ;j++)
if(i!=j)
for(int k=i+;k<=equ;k++) ratio[j][k]-=ratio[j][i]*ratio[i][k];
}
return true;
}
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
equ=n*m;
for(int i=;i<n;i++)
{
scanf("%s",&s);
for(int j=;j<strlen(s);j++)
{
map[i][j]=s[j];
if(s[j]=='D') {map[i][j]='.';sx=i;sy=j;}
if(s[j]=='E') {map[i][j]='.';ex=i;ey=j;}
}
}
Bfs(sx,sy);
Reset();
bool ok=Gauss();
if(ok&&ratio[sx*n+sy][equ]<=) printf("%.2lf\n",ratio[sx*n+sy][equ]);
else printf("tragedy!\n");
memset(ratio,,sizeof(ratio));
memset(vis,,sizeof(vis));
}
}
| 2709 | 2013217098 | Accepted |
1148
|
88
|
C++ | 2668 B | 2014-11-06 20:51:07 |