Cod sursa(job #1413359)

Utilizator felixiPuscasu Felix felixi Data 1 aprilie 2015 20:30:43
Problema Minesweeper Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <stdio.h>
#include <iostream>
#include <iomanip>

#define NLen 32
#define MLen 512

using namespace std;

int conf[NLen][NLen];

double E[MLen][MLen];
long double tm[MLen];

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

    int N,M;

    cin>>N>>M;

    N*=M;
    M=0;

    for(int i=0;i<=N;++i)
        for(int j=0;i+j<=N;++j)
            conf[i][j]=++M;

    ++M;

    for(int b=0;b<=N;++b)
        for(int c=0;b+c<=N;++c)
        {
            int a=N-b-c;

            E[conf[b][c]][conf[b][c]]=1;

            if(c==N) continue;

            E[conf[b][c]][M]=1;

            if(a) E[conf[b][c]][conf[b+1][c]]-=(double)a/N;

            if(b) E[conf[b][c]][conf[b-1][c+1]]-=(double)b/N;

            if(c) E[conf[b][c]][conf[b][c-1]]-=(double)c/N;
        }

    for(int i=1;i<M;++i)
    {
        if(E[i][i]!=0)
        {
            for(int j=i+1;j<=M;++j) E[i][j]/=E[i][i];
            E[i][i]=1;
        }

        for(int k=i+1;k<M;++k)
            if(E[k][i]!=0)
            {
                for(int j=i+1;j<=M;++j) E[k][j]-=E[k][i]*E[i][j];
                E[k][i]=0;
            }
    }

    for(int i=M;i>0;--i)
    {
        tm[i]=E[i][M];

        for(int j=i+1;j<M;++j)
            tm[i]-=E[i][j]*tm[j];
    }

    cout<<fixed<<setprecision(6)<<tm[1]<<'\n';

    return 0;
}