Cod sursa(job #645069)

Utilizator crushackPopescu Silviu crushack Data 8 decembrie 2011 11:21:05
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <stdio.h>
#include <algorithm>
#define NMax 30
using namespace std;

const char IN[]="minesweeper.in",OUT[]="minesweeper.out";

int N,M,L,C,sol;
int T[NMax][NMax];
double v[NMax*NMax];
double Mat[NMax*NMax][NMax*NMax];
double rez[NMax*NMax];

void swapRow(int x,int y){
	for (int i=1;i<=L+1;++i)
		swap(Mat[x][i],Mat[y][i]);
}

void gauss()
{
	int i,j,k,l;
	
	for (i=1,j=1;i<=L;++i)
	{
		if (!Mat[i][j])
		{
			for (k=i+1;k<=L && !Mat[k][i];++k);
			if (k<=L) swapRow(k,i);
		}
		
		for (l=i+1;l<=L;++l)
		{
			if (Mat[l][j]==0) continue;
			double r=Mat[l][j]/Mat[i][j];
			for (k=1;k<=L+1;++k)
				Mat[l][k]-= Mat[i][k]*r;
		}
		
		++j;
	}
	
	for (i=L;i>0;--i)
	{
		rez[i]=Mat[i][L+1];
		for (j=L;j>i;--j)
			rez[i]-=Mat[i][j]*rez[j];
		rez[i]/=Mat[i][i];
	}
}

int main()
{
	int i,j,c;
	freopen(IN,"r",stdin);
	scanf("%d%d",&N,&M);
	fclose(stdin);
	
	N*=M;
	
	for (i=0,c=0;i<=N;++i) for (j=0;i+j<=N;++j) 
		T[i][j]=++c;
	L=c;
	Mat[1][1]=1;
	for (i=0;i<=N;++i)
		for (j=(i==0);i+j<=N;++j)
		{
			if (i+j<N) Mat[T[i][j]][T[i+1][j]]= -(N-i-j)/(double)N;
			if (i)     Mat[T[i][j]][T[i-1][j+1]]= -i/(double)N ;
			if (j)     Mat[T[i][j]][T[i][j-1]]= -j/(double)N ;
			Mat[T[i][j]][T[i][j]]=1;
			Mat[T[i][j]][L+1]=1;
			
		}
		
	gauss();
	
	freopen(OUT,"w",stdout);
	printf("%lf\n",rez[L]);
	fclose(stdout);
	return 0;
}