Cod sursa(job #1251173)

Utilizator george_stelianChichirim George george_stelian Data 28 octombrie 2014 23:56:42
Problema Minesweeper Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const double eps=0.000000001;
double v[500][500];
int cod[25][25];

int main()
{
    freopen("minesweeper.in", "r", stdin);
    freopen("minesweeper.out", "w", stdout);
    int n,m,nr=0;
    scanf("%d%d",&n,&m);
    n*=m;
    for(int i=0;i<=n;i++)
    {
        int lim=n-i;
        for(int j=0;j<=lim;j++) cod[i][j]=++nr;
    }
    for(int i=0;i<=n;i++)
    {
        int lim=n-i;
        for(int j=0;j<=lim;j++)
        {
            v[cod[i][j]][cod[i][j]]=v[cod[i][j]][nr+1]=1;
            if(i) v[cod[i][j]][cod[i-1][j+1]]=(double)-i/n;
            if(j) v[cod[i][j]][cod[i][j-1]]=(double)-j/n;
            if(n-i-j) v[cod[i][j]][cod[i+1][j]]=(double)-(n-i-j)/n;
        }
    }
    int i=2,j=1,q;
    while(i<=nr && j<=nr)
    {
        for(q=i;q<=nr;q++) if(abs(v[q][j])>eps) break;
        if(q==nr+1) {j++;continue;}
        if(q>i) for(int k=1;k<=nr+1;k++) swap(v[i][k],v[q][k]);
        for(q=i+1;q<=nr;q++)
        {
            double x=v[q][j]/v[i][j];
            for(int k=j;k<=nr+1;k++) v[q][k]-=v[i][k]*x;
        }
        i++;j++;
    }
    printf("%lf",v[nr][nr+1]/v[nr][nr]);
    return 0;
}