Cod sursa(job #674705)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 6 februarie 2012 17:36:19
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>

using namespace std;

#define maxn 410

int n, nr, c;
double v[maxn][maxn];
int pz[maxn][maxn];

int main()
{
    freopen("minesweeper.in", "r", stdin);
    freopen("minesweeper.out", "w", stdout);

    scanf("%d%d", &n, &nr);
    n*=nr; nr=0;

    for(int i=0; i<=n; ++i)
        for(int j=0; i+j<=n; ++j)
            pz[i][j]=++nr;

    for(int i=0; i<=n; ++i)
        for(int j=0; i+j<=n; ++j)
        {
            if(i==0 && j==0)
            {
                v[1][1]=1;
                continue;
            }

            c=pz[i][j];

            v[c][nr+1]=v[c][c]=n;
            if(i>0)
                v[c][pz[i-1][j+1]]=-i;
            if(j>0)
                v[c][pz[i][j-1]]=-j;
            if(i+j<=n)
                v[c][pz[i+1][j]]=-(n-i-j);
        }

    for(int i=1; i<=nr; ++i)
        for(int j=i+1; j<=nr; ++j)
            for(int k=nr+1; k>=i; --k)
                v[j][k]-=v[j][i]/v[i][i]*v[i][k];

    printf("%.6lf\n", v[nr][nr+1]/v[nr][nr]);

    return 0;
}