Cod sursa(job #821133)

Utilizator rvnzphrvnzph rvnzph Data 21 noiembrie 2012 19:37:10
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <stdio.h>
#include <iostream>
#include <iomanip>

#define NLen 32
#define MLen 512

using namespace std;

int conf[NLen][NLen];

double E[MLen][MLen];
long 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)
		{			
			int a=N-b-c;
			
			E[conf[b][c]][conf[b][c]]=1;
			
			if(c==N) continue;
			
			E[conf[b][c]][M]=1;
			
			if(a) E[conf[b][c]][conf[b+1][c]]-=(double)a/N;
			
			if(b) E[conf[b][c]][conf[b-1][c+1]]-=(double)b/N;
			
			if(c) E[conf[b][c]][conf[b][c-1]]-=(double)c/N;
		}
		
	for(int i=1;i<M;++i)
	{
		if(E[i][i]!=0)
		{
			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(E[k][i]!=0)
			{
				for(int j=i+1;j<=M;++j) E[k][j]-=E[k][i]*E[i][j];
				E[k][i]=0;
			}
	}

	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';
		
	return 0;
}