Cod sursa(job #1969548)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 18 aprilie 2017 15:20:06
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const double eps=0.00000001;
int n,m,vaz[25][25],c=0;
double v[600][600],sol[600];

void gauss()
{
    int i=1,j=1;
    while(i<=c && j<=c)
    {
        int k;
        for(k=i;k<=c && abs(v[k][j])<eps;k++);
        if(k>c) {j++;continue;}
        swap(v[i],v[k]);
        for(int k=i+1;k<=c;k++)
        {
            double p=v[k][j]/v[i][j];
            for(int q=j;q<=c+1;q++) v[k][q]-=p*v[i][q];
            v[k][j]=0;
        }
        i++;j++;
    }
    for(int i=c;i>=1;i--)
        for(int j=1;j<=c+1;j++)
            if(abs(v[i][j])>eps)
            {
                sol[j]=v[i][c+1];
                for(int k=j+1;k<=c;k++) sol[j]-=sol[k]*v[i][k];
                sol[j]/=v[i][j];
                break;
            }
}

int main()
{
    freopen("minesweeper.in","r",stdin);
    freopen("minesweeper.out","w",stdout);
    scanf("%d%d",&n,&m);
    n*=m;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n-i;j++)
            vaz[i][j]=++c;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n-i;j++)
            if(i<n)
            {
                int k=vaz[i][j];
                if(i>0) v[k][vaz[i-1][j+1]]=-(1.0*i/n);
                if(j>0) v[k][vaz[i][j-1]]=-(1.0*j/n);
                if(n-i-j>0) v[k][vaz[i+1][j]]=-(1.0*(n-i-j))/n;
                v[k][k]=v[k][c+1]=1;
            }
    gauss();
    printf("%.8f",sol[vaz[0][n]]);
    return 0;
}