Cod sursa(job #820566)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 21 noiembrie 2012 00:45:49
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include<stdio.h>

#define maxn 23

FILE*f=fopen("minesweeper.in","r");
FILE*g=fopen("minesweeper.out","w");

const double err = 1e-12;
int n,index,N;
int ind[maxn][maxn],x[maxn*maxn],y[maxn*maxn];
double A[maxn*maxn][maxn*maxn],sol[maxn][maxn];

inline void variables () {
	
	for ( int libere = 0 ; libere <= n ; ++libere ){
		for ( int steag = 0 ; libere + steag <= n ; ++steag ){
			ind[libere][steag] = ++index;
			x[index] = libere; y[index] = steag;
		}
	}
}

inline void build_eqs () {
	
	for ( int libere = 0 ; libere <= n ; ++libere ){
		for ( int steag = 0 ; steag + libere <= n ; ++steag ){
			
			int ask = n-libere-steag,where = ind[libere][steag];
			A[where][where] = 1;
			if ( ask == n )	continue ;
			if ( libere > 0 ){
				A[ ind[libere][steag] ][ ind[libere-1][steag+1] ] -= (double)libere/n;
				A[ ind[libere][steag] ][index+1] += (double)libere/n;
			}
			if ( steag > 0 ){
				A[ ind[libere][steag] ][ ind[libere][steag-1] ] -= (double)steag/n;
				A[ ind[libere][steag] ][index+1] += (double)steag/n;
			}
			if ( ask > 0 ){
				A[ ind[libere][steag] ][ ind[libere+1][steag] ] -= (double)ask/n;
				A[ ind[libere][steag] ][index+1] += (double)ask/n;
			}
		}
	}
}

inline bool equal ( const double &a , const double &b ){
	double dif = a-b;
	if ( dif < 0 )	dif = -dif;
	return dif < err;
}

inline void swap_lines ( double *A , double *B ){
	
	for ( int i = 1 ; i <= N+1 ; ++i ){
		double aux = A[i];
		A[i] = B[i];
		B[i] = aux;
	}
}

inline void gauss () {

	int i = 1,j = 1; N = index;
	while ( i <= N && j <= N ){
		
		int index;
		for ( index = i ; index <= N ; ++index ){
			if ( !equal(A[index][j],0.0) ){
				break ;
			}
		}
		if ( index == N+1 ){
			++j; continue ;
		}
		
		swap_lines(A[i],A[index]);
		
		for ( int index = j + 1 ; index <= N+1 ; ++index ){
			A[i][index] /= A[i][j];
		}
		A[i][j] = 1;
		
		for ( int index = i+1 ; index <= N ; ++index ){
			double m = A[index][j];
			if ( equal(A[index][j],0) )	continue ;
			for ( int k = j ; k <= N+1 ; ++k ){
				A[index][k] = A[i][k]*m - A[index][k];
			}
		}
		++i; ++j;
	}
}

int main () {
	
	int x,y;
	fscanf(f,"%d %d",&x,&y);
	n = x * y;
	
	variables();
	build_eqs();
	gauss();
	
	fprintf(g,"%lf\n",A[N][N+1]);
	
	fclose(f);
	fclose(g);
	
	return 0;
}