Pagini recente » Cod sursa (job #1060879) | Cod sursa (job #2185953) | Cod sursa (job #1352528) | Cod sursa (job #1061874) | Cod sursa (job #820879)
Cod sursa(job #820879)
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <iomanip>
#include <math.h>
#define NLen 32
#define MLen 512
#define EPS 0.000001
using namespace std;
int conf[NLen][NLen];
long double E[MLen][MLen];
long double tm[MLen];
int main()
{
freopen("minesweeper.in","r",stdin);
freopen("minesweeper.out","w",stdout);
int M,N;
cin>>N>>M;
N*=M;
M=0;
for(int i=0;i<=N;++i)
for(int j=0;i+j<=N;++j)
conf[i][j]=++M;
++M;
for(int i=0;i<=N;++i)
for(int j=0;i+j<=N;++j)
{
E[conf[i][j]][conf[i][j]]=1;
if(j==N) continue;
if(N-i-j>0)
{
double p=N-i-j;
p/=N;
E[conf[i][j]][conf[i+1][j]]-=p;
E[conf[i][j]][M]+=p;
}
if(i>0)
{
double p=i;
p/=N;
E[conf[i][j]][conf[i-1][j+1]]-=p;
E[conf[i][j]][M]+=p;
}
if(j>0)
{
double p=j;
p/=N;
E[conf[i][j]][conf[i][j-1]]-=p;
E[conf[i][j]][M]+=p;
}
}
for(int i=1;i<M;++i)
{
if(fabs(E[i][i]-1)>EPS)
{
for(int j=i+1;j<=M;++j) E[i][j]/=E[i][i];
E[i][i]/=E[i][i];
}
for(int r=i+1;r<M;++r)
if(fabs(E[r][i])>EPS)
{
for(int j=i+1;j<=M;++j)
E[r][j]-=E[r][i]*E[i][j];
E[r][i]-=E[i][i]*E[r][i];
}
}
memset(tm,0,sizeof(tm));
for(int i=M;i>0;--i)
{
tm[i]=E[i][M];
for(int j=M-1;j>i;--j)
tm[i]-=E[i][j]*tm[j];
}
cout<<fixed<<setprecision(6)<<tm[conf[0][0]]<<'\n';
return 0;
}