Pagini recente » Cod sursa (job #1531280) | Cod sursa (job #716879) | Cod sursa (job #1167769) | Cod sursa (job #1639430) | Cod sursa (job #820566)
Cod sursa(job #820566)
#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;
}