Cod sursa(job #635013)

Utilizator cezar305Mr. Noname cezar305 Data 18 noiembrie 2011 10:18:44
Problema Minesweeper Scor Ascuns
Compilator cpp Status done
Runda Marime 1.03 kb
#include<stdio.h>

#define MAXN 25
#define MAXE 25*25

double A[MAXE][MAXE];
int T[MAXN][MAXN];
int i,j,N,M,stari,x,k;

int main()
{
	freopen("minesweeper.in","r",stdin);
	freopen("minseweeper.out","w",stdout);
	
	scanf("%d %d",&N,&M); N *= M;
	
	// T[i][j] = i goale, j stegulete
	stari = 0;
	for (i = 0; i <= N; ++i)
		for (j = 0; i + j <= N; ++j)
			T[i][j] = stari++;

	A[0][0] = 1.0;
	for (i = 0; i <= N; ++i)
		for (j = 0; i + j <= N; ++j){
			if (i == 0 && j == 0)
				continue;
		
			x = T[i][j];
			if (i > 0)
				A[x][ T[i-1][j+1] ] = -1.0 * i;
			if (j > 0)
				A[x][ T[i][j-1] ] = -1.0 * j;
			if (i + j < N)
				A[x][ T[i+1][j] ] = -1.0 * (N - i - j);
			A[x][x] = 1.0 * N;
			A[x][stari] = 1.0 * N;
		}
		
	for (i = 0; i < stari; ++i)
		for (j = 0; j < stari; ++j)
			if (i!=j){
				double raport = A[j][i]/A[i][i];
				for (k = i; k<=stari; ++k)
					A[j][k] -= raport * A[i][k];
			}
	
	double Ans = 1.0 * A[stari-1][stari] / A[stari-1][stari-1];
	printf("%.6lf\n", Ans);
	return 0;
}