Cod sursa(job #821121)

Utilizator rvnzphrvnzph rvnzph Data 21 noiembrie 2012 19:00:27
Problema Minesweeper Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <iomanip>

#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("minesweeper.out","w",stdout);
	
	int N,M;
	
	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 b=0;b<=N;++b)
		for(int c=0;b+c<=N;++c)
		{
			if(c==N) continue;
			
			int a=N-b-c;
			
			E[conf[b][c]][conf[b][c]]=1;
			E[conf[b][c]][M]=1;
			
			if(a)
			{
				double p=a;
				p/=N;
				
				E[conf[b][c]][conf[b+1][c]]-=p;
			}
			
			if(b)
			{
				double p=b;
				p/=N;
				
				E[conf[b][c]][conf[b-1][c+1]]-=p;
			}
			
			if(c)
			{
				double p=c;
				p/=N;
				
				E[conf[b][c]][conf[b][c-1]]-=p;
			}
		}
		
	for(int i=1;i<M;++i)
	{
		if(fabs(E[i][i])>EPS)
		{
			for(int j=i+1;j<=M;++j) E[i][j]/=E[i][i];
			E[i][i]=1;
		}
		
		for(int k=i+1;k<M;++k)
			if(fabs(E[k][i])>EPS)
			{
				for(int j=i+1;j<=M;++j) E[k][j]-=E[k][i]*E[i][j];
				E[k][i]=0;
			}
	}
	
	/*for(int i=1;i<M;++i)
	{
		for(int j=1;j<=M;++j) cout<<E[i][j]<<' ';
		cout<<'\n';
	}*/
	
	for(int i=M;i>0;--i)
	{
		tm[i]=E[i][M];
		
		for(int j=i+1;j<M;++j)
			tm[i]-=E[i][j]*tm[j];
	}
	
	cout<<fixed<<setprecision(6)<<tm[1]<<'\n';
	
	/*cout<<"***\n";
	for(int i=1;i<M;++i) cout<<tm[i]<<'\n';*/
		
	return 0;
}