Cod sursa(job #636184)

Utilizator AndrewTheGreatAndrei Alexandrescu AndrewTheGreat Data 19 noiembrie 2011 17:38:35
Problema Minesweeper Scor 30
Compilator cpp Status done
Runda .com 2011 Marime 1.5 kb
#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

const int nmax = 25;
double C[2][nmax][nmax][nmax];

inline double fabs(double x)
{
    if(x < 0)
        return -x;
    else return x;
}

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

    int N, n, m, i, j, pas, x = 0, flag;
    double Rez = 0, pondere = 0, last = -1, Tot = 0;

    scanf("%d %d", &n, &m);
    N = n * m;

    C[0][N][0][0] = 1;
    pas = 0;
    while(1)
    {
        pas++;
        for(i = 0; i <= N; i++)
            for(j = 0; j <= N - i; j++)
                if(C[x][i][j][N - i - j])
                {
                    if(i)
                        C[1 - x][i - 1][j + 1][N - i - j] += ((i * C[x][i][j][N - i - j]) / N);
                    if(j)
                        C[1 - x][i][j - 1][N - i - j + 1] += ((j * C[x][i][j][N - i - j]) / N);
                    if(N - i - j)
                        C[1 - x][i + 1][j][N - i - j - 1] += (((N - i - j) * C[x][i][j][N - i - j]) / N);
                }

        if(C[1 - x][0][0][N])
        {

            Rez += pas * C[1 - x][0][0][N];
            pondere += C[1 - x][0][0][N];
            C[1 - x][0][0][N] = 0;
            if(fabs(Tot - Rez/pondere) < 1e-12)
                break;
            Tot = Rez / pondere;
        }

        x = 1 - x;

        memset(C[1 - x], 0, sizeof(C[1 - x]));
    }

    printf("%.6lf\n", Tot);


    return 0;
}