Cod sursa(job #820816)

Utilizator rvnzphrvnzph rvnzph Data 21 noiembrie 2012 10:57:00
Problema Minesweeper Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#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]]=N;
			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;
}