Cod sursa(job #639774)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 23 noiembrie 2011 22:39:43
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <stdio.h>
#include <algorithm>
#define f first
#define s second
#define NMAX 23
#define LMAX 305
using namespace std;
int n,m,A[NMAX][NMAX],r,stare_i;
pair <int,int> B[LMAX];
double C[LMAX][LMAX],rez[LMAX];
void code_entities()
{
	int i,j;
	for (i=0; i<=n; i++)
		for (j=0; j<=n-i; j++)
		{
			A[i][j]=++r;
			B[r].f=i; B[r].s=j;
			if (i==n && j==0)
				stare_i=r;
		}
}
void make_recurrence()
{
	int i,x,y;
	C[1][1]=1;
	for (i=2; i<=r; i++)
	{
		x=B[i].f; y=B[i].s;
		if (x)
			C[i][A[x-1][y+1]]=-(double)x/n;
		if (y)
			C[i][A[x][y-1]]=-(double)y/n;
		if (n-x-y)
			C[i][A[x+1][y]]=-(double)(n-x-y)/n;
		C[i][i]=1; C[i][r+1]=1;
	}
}
void do_gauss()
{
	int i,j,k;
	double fact;
	for (i=1; i<=r; i++)
	{
		for (j=i+1; j<=r; j++)
		{
			fact=C[j][i]/C[i][i];
			for (k=i; k<=r+1; k++)
				C[j][k]-=C[i][k]*fact;
		}
	}
	for (i=r; i>=1; i--)
	{
		rez[i]=C[i][r+1];
		for (j=i+1; j<=r; j++)
			rez[i]-=C[i][j]*rez[j];
		rez[i]/=C[i][i];
	}
}
int main()
{
	freopen("minesweeper.in","r",stdin);
	freopen("minesweeper.out","w",stdout);
	scanf("%d%d",&n,&m);
	n*=m;
	code_entities();
	make_recurrence();
	do_gauss();
	printf("%lf\n",rez[stare_i]);
	return 0;
}