Cod sursa(job #818787)

Utilizator rvnzphrvnzph rvnzph Data 17 noiembrie 2012 23:27:12
Problema Minesweeper Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <math.h>

#define EPS 0.000001
#define NLen 512
#define nLen 32

using namespace std;

double E[NLen][NLen];

int stare[nLen][nLen];

double tm[NLen];

int main()
{
	freopen("minesweeper.in","r",stdin);
	freopen("minesweeper.out","w",stdout);
	
	int N,num,final;
	
	cin>>N>>num;
	N*=num;
	
	num=0;
	for(int a=0;a<=N;++a)
		for(int b=0;a+b<=N;++b)
		{
			stare[a][b]=++num;
			if(b==N) final=num;
		}
	++num;
			
	for(int a=0;a<=N;++a)
		for(int b=0;a+b<=N;++b)
		{
			E[stare[a][b]][stare[a][b]]=1;
			
			if(a>0)
			{
				double p01=N-a-b+1;
				p01/=N;
				E[stare[a][b]][stare[a-1][b]]-=p01;
				E[stare[a][b]][num]+=p01;
			}
			
			if(b>0)
			{
				double p12=a+1;
				p12/=N;
				E[stare[a][b]][stare[a+1][b-1]]-=p12;
				E[stare[a][b]][num]+=p12;
			}

			if(N-a-b>=1)
			{
				double p20=b+1;
				p20/=N;
				E[stare[a][b]][stare[a][b+1]]-=p20;
				E[stare[a][b]][num]+=p20;
			}
		}
		
	for(int i=1;i<num;++i)
	{
		for(int j=1;j<=num;++j) cout<<E[i][j]<<' ';
		cout<<'\n';
	}
		
	for(int i=1;i<num;++i)
	{
		if(E[i][i]!=1)
		{
			for(int j=i+1;j<=num;++j) E[i][j]/=E[i][i];
			E[i][i]=1;
		}
		
		for(int r=i+1;r<num;++r)
			if(fabs(E[r][i])>EPS)
			{
				for(int c=i+1;c<=num;++c) E[r][c]-=E[r][i]*E[i][c];
				E[r][i]=0;
			}
	}
	
	for(int i=num-1;i>=final;--i)
	{
		tm[i]=E[i][num];
		for(int j=i+1;j<num;++j)
			tm[i]-=tm[j]*E[i][j];
	}
	
	cout<<fixed<<setprecision(6)<<tm[final]<<'\n';
	
	return 0;
}