Cod sursa(job #1791183)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 29 octombrie 2016 10:30:02
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#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);
    q=0;
    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;
            }
        }
    }
    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;
}