Pagini recente » Cod sursa (job #2149658) | Cod sursa (job #436747) | Cod sursa (job #2844845) | Cod sursa (job #2843872) | Cod sursa (job #1791180)
#include <cstdio>
#define EPS 0.0000001
#define MAXN 22
#define MAXK 276
bool viz[MAXK+1];
int cine[MAXN+1][MAXN+1];
double a[MAXK+1][MAXK+2], ans[MAXK+1];
int main(){
int n, m, k, q, l;
double aux, r;
FILE *fin, *fout;
fin=fopen("minesweeper.in", "r");
fout=fopen("minesweeper.out", "w");
fscanf(fin, "%d%d", &n, &m);
n*=m;
k=0;
for(int i=0; i<=n; i++)
for(int j=0; i+j<=n; j++)
cine[i][j]=(++k);
for(int i=0; i<=n; i++){
for(int j=0; i+j<=n; j++){
q++;
a[q][cine[i][j]]=1;
if((i>0)||(j>0)){
a[q][k+1]=1;
if(i>0) a[q][cine[i-1][j+1]]=-i/(double)n;
if(j>0) a[q][cine[i][j-1]]=-j/(double)n;
if(i+j<n) a[q][cine[i+1][j]]=-(n-i-j)/(double)n;
}
}
}
return 0;
int i=1, j=1;
while((i<=q)&&(j<=k)){
l=i;
while((l<=q)&&((a[l][j]<EPS)&&(a[l][j]>-EPS)))
l++;
if(l>q) j++;
else{
if(i!=l){
for(int p=1; p<=k+1; p++){
aux=a[i][p];
a[i][p]=a[l][p];
a[l][p]=aux;
}
}
for(int p=j+1; p<=k+1; p++)
a[i][p]/=a[i][j];
a[i][j]=1;
for(int p=i+1; p<=q; p++){
for(int u=j+1; u<=k+1; u++)
a[p][u]-=a[p][j]*a[i][u];
a[p][j]=0;
}
i++;
j++;
}
}
for(i=q; i>0; i--){
j=k;
r=a[i][k+1];
while((j>0)&&((viz[j])||((a[i][j]>-EPS)&&(a[i][j]<EPS)))){
r-=a[i][j]*ans[j];
j--;
}
if(j>0) ans[j]=r, viz[j]=1;
}
fprintf(fout, "%.6lf\n", ans[cine[n][0]]);
fclose(fin);
fclose(fout);
return 0;
}