文件详细信息

下载本文件

本文件的大小为 1651 字节。

#include<algorithm>
#include<cmath>
#include<cstdio>
typedef double real;
const int maxn=10000,maxm=20,dx[]={-1,1,0,0},dy[]={0,0,-1,1};
const real eps=1e-10;
int p[4],n,m,tot,mv[maxn*maxm],id[maxn][maxm];
bool q[maxn][maxm];
real tA[maxn*maxm][maxm*2+1],B[maxn*maxm],st;
real&A(const int x,const int y){
	return tA[x][y-mv[x]];
}
bool inside(const int a,const int b){
	return a>=0&&a<n&&b>=0&&b<m;
}
void gauss(){
	for(int k=0;k<tot;k++){
		if(fabs(A(k,k))<eps)continue;
		const int t=std::min(tot-1,k+m);
		B[k]/=A(k,k);
		for(int i=t;i>=k;i--)A(k,i)/=A(k,k);
		for(int i=k+1;i<=t;i++){
			B[i]-=B[k]*A(i,k);
			for(int j=t;j>=k;j--)A(i,j)-=A(k,j)*A(i,k);
		}
	}
	for(int i=tot-1;i>=0;i--)
		for(int j=i+1,t=std::min(tot-1,i+m);j<=t;j++)
			B[i]-=A(i,j)*B[j];
}
int main(){
	scanf("%d%d",&m,&n);
	scanf("%d%d%d%d",p+0,p+1,p+2,p+3);
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++){
			char c;
			do c=getchar();
			while(c!='X'&&c!='T'&&c!='.');
			id[i][j]=c!='X'?tot++:-1;
			if(c=='T')q[i][j]=true;
		}
	for(int i=0;i<tot;i++)mv[i]=std::max(0,i-m);
	{
		int cnt=0;
		for(int j=0;j<m;j++)cnt+=id[0][j]!=-1;
		st=1.0/cnt;
	}
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++){
			if(id[i][j]==-1)continue;
			int&t=id[i][j];
			if(!i)B[t]=st;
			A(t,t)=1;
			if(q[i][j])continue;
			int tot=0;
			for(int k=0,nx,ny;k<4;k++){
				nx=i+dx[k],ny=j+dy[k];
				if(inside(nx,ny)&&id[nx][ny]!=-1)tot+=p[k];
			}
			for(int k=0,nx,ny;k<4;k++){
				nx=i+dx[k],ny=j+dy[k];
				if(inside(nx,ny)&&id[nx][ny]!=-1)A(id[nx][ny],t)=-(real)p[k]/tot;
			}
		}
	gauss();
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			if(q[i][j])
				printf("%.9lf\n",B[id[i][j]]);
	return 0;
}