Cod sursa(job #820879)

Utilizator rvnzphrvnzph rvnzph Data 21 noiembrie 2012 12:18:34
Problema Minesweeper Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#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;
}