Cod sursa(job #638107)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 20 noiembrie 2011 18:54:35
Problema Minesweeper Scor 0
Compilator cpp Status done
Runda .com 2011 Marime 0.75 kb
#include <cstdio>

#define NMax 23
#define MMax 2000

using namespace std;

int N;
double DP[MMax][NMax][NMax], S;

void Read ()
{
    freopen ("minesweeper.in", "r", stdin);
    int n, m;
    scanf ("%d %d", &n, &m);
    N=n*m;
}

void Print ()
{
    freopen ("minesweeper.out", "w", stdout);
    printf ("%.6lf\n", S);
}

int main()
{
    Read ();
    DP[0][0][0]=1;
    for (int m=1; m<MMax; ++m)
    {
        for (int F=0; F<=N; ++F)
        {
            for (int Q=0; F+Q<=N; ++Q)
            {
                int E=N-Q-F;
                DP[m][F][Q]=(DP[m-1][F-1][Q]*(E+1)+DP[m-1][F][Q+1]*(Q+1)+DP[m-1][F+1][Q-1]*(F+1))/N;
            }
        }
        S+=(m*DP[m][0][N]);
    }
    Print ();
    return 0;
}