Cod sursa(job #677638)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 10 februarie 2012 14:24:08
Problema Minesweeper Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <cstdio>
#include <cstring>

#define StepMax 100000
#define NMax 23

using namespace std;

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

void Solve ()
{
    DP[0][N][0]=1;
	for (int Step=1; Step<=StepMax; ++Step)
	{
		for (int E=0; E<=N; ++E)
		{
			for (int F=0; F<=N-E; ++F)
			{
                int Q=N-E-F;
                if (Q==N)
                {
                    continue;
                }
                if (E>0)
                {
                    DP[1][E-1][F+1]+=(1.0*E)/(1.0*N)*DP[0][E][F];
                }

                if (F>0)
                {
                    DP[1][E][F-1]+=(1.0*F)/(1.0*N)*DP[0][E][F];
                }

                if (Q>0)
                {
                    DP[1][E+1][F]+=(1.0*Q)/(1.0*N)*DP[0][E][F];
                }
			}
        }
        S+=(Step*DP[1][0][0]);
        memcpy (DP[0], DP[1], sizeof (DP[0]));
        memset (DP[1], 0, sizeof (DP[1]));
	}
}

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

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

int main ()
{
    Read ();
    Solve ();
    Print ();
	return 0;
}