Cod sursa(job #820706)

Utilizator rvnzphrvnzph rvnzph Data 21 noiembrie 2012 09:36:47
Problema Minesweeper Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#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;
}