Pagini recente » Cod sursa (job #3199657) | Cod sursa (job #2955960) | Cod sursa (job #2648821) | Cod sursa (job #1043657) | Cod sursa (job #820706)
Cod sursa(job #820706)
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <math.h>
#define NLen 32
#define MLen 512
#define EPS 0.000001
using namespace std;
int conf[NLen][NLen];
double E[MLen][MLen];
double tm[MLen];
int main()
{
freopen("minesweeper.in","r",stdin);
freopen("minsweeper.out","w",stdout);
int M,N;
cin>>N>>M;
N*=M;
M=0;
for(int a=0;a<=N;++a)
for(int b=0;a+b<=N;++b)
conf[a][b]=++M;
++M;
for(int a=0;a<=N;++a)
for(int b=0;a+b<=N;++b)
{
E[conf[a][b]][conf[a][b]]=1;
if(N-a-b>0&&b+1!=N)
{
double p=b+1;
p/=N;
E[conf[a][b]][conf[a][b+1]]-=p;
E[conf[a][b]][M]+=p;
}
if(a>0)
{
double p=N-a-b+1;
p/=N;
E[conf[a][b]][conf[a-1][b]]-=p;
E[conf[a][b]][M]+=p;
}
if(b>0)
{
double p=a+1;
p/=N;
E[conf[a][b]][conf[a+1][b-1]]-=p;
E[conf[a][b]][M]+=p;
}
}
for(int row=1,col=1;row<M&&col<M;)
{
if(fabs(E[row][col])<=EPS)
{
++col;
continue;
}
if(fabs(E[row][col]-1)>EPS)
{
for(int j=col+1;j<=M;++j) E[row][j]/=E[row][col];
E[row][col]=1;
}
for(int i=row+1;i<M;++i)
if(fabs(E[i][col])>EPS)
{
for(int j=col+1;j<=M;++j)
E[i][j]-=E[row][j]*E[i][col];
E[i][col]=0;
}
++col;
++row;
}
memset(tm,0,sizeof(tm));
for(int row=M;row>0;--row)
{
tm[row]=E[row][M];
int j;
for(j=1;j<M&&fabs(E[row][j])<=EPS;++j);
for(++j;j<M;++j)
tm[row]-=tm[j]*E[row][j];
if(row==conf[0][N]) break;
}
cout<<fixed<<setprecision(6)<<tm[conf[0][N]]<<'\n';
return 0;
}