Pagini recente » Cod sursa (job #1393344) | Cod sursa (job #2568943) | Cod sursa (job #168456) | Cod sursa (job #2903769) | Cod sursa (job #820814)
Cod sursa(job #820814)
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <iomanip>
#include <math.h>
#define EPS 0.000001
#define NLen 32
#define MLen 512
using namespace std;
double E[MLen][MLen];
int conf[NLen][NLen];
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;
// N = numarul de celule ale jocului
// M = va fi numarul de configuratii diferite pe care le va avea jocul
int seek_n_destroy; // numarul configuratiei cand jocul va avea numai semne de intrebare
for(int a=0;a<=N;++a)
for(int b=0;a+b<=N;++b)
{
conf[a][b]=++M;
if(b==N) seek_n_destroy=M;
}
++M;
memset(E,0,sizeof(E));
for(int a=0;a<=N;++a)
for(int b=0;a+b<=N;++b)
{
E[conf[a][b]][conf[a][b]]=3;
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;
}
if(N-a-b>0)
{
double p=b+1;
p/=N;
E[conf[a][b]][conf[a][b+1]]-=p;
E[conf[a][b]][M]+=p;
}
}
// Gauss
memset(tm,0,sizeof(tm));
int row,col;
for(row=1,col=1;row<M&&col<M;)
{
if(fabs(E[row][col])<=EPS)
{
int pos=0;
for(int i=row+1;i<M;++i)
if(fabs(E[i][col])>EPS)
{
pos=i;
break;
}
if(pos==0)
{
++col;
continue;
}
for(int j=col;j<=M;++j)
{
double aux=E[row][j];
E[row][j]=E[pos][j];
E[pos][j]=aux;
}
if(row==seek_n_destroy) seek_n_destroy=pos;
else
if(pos==seek_n_destroy) seek_n_destroy=row;
}
if(E[row][col]!=1)
{
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;
}
++row;
++col;
}
if(seek_n_destroy>row)
{
cout<<"Nasol\n";
return 0;
}
for(;row>=1;--row)
{
tm[row]=E[row][M];
int j;
for(j=1;j<M;++j)
if(fabs(E[row][j])>EPS) break;
for(++j;j<M;++j)
tm[row]-=tm[j]*E[row][j];
}
cout<<fixed<<setprecision(6)<<tm[seek_n_destroy]<<'\n';
return 0;
}