Cod sursa(job #636334)

Utilizator AndrewTheGreatAndrei Alexandrescu AndrewTheGreat Data 19 noiembrie 2011 18:56:17
Problema Minesweeper Scor 0
Compilator cpp Status done
Runda .com 2011 Marime 2.56 kb
#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

const int nmax = 25;
double C[2][nmax][nmax][nmax];
int Q[2][10000][3];
int pq[2], uq[2];

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, a, b, c;
    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;
    Q[x][0][0] = 3;
    while(1)
    {
        pas++;
        while(pq[x] <= uq[x])
        {
            a = Q[x][pq[x]][0];
            b = Q[x][pq[x]][1];
            c = Q[x][pq[x]][2];

            if(C[x][a][b][c])
            {
                if(a)
                {
                    if(C[1 - x][a - 1][b + 1][c] == 0)
                    {
                        Q[1 - x][++uq[1 - x]][0] = a - 1;
                        Q[1 - x][uq[1 - x]][1] = b + 1;
                        Q[1 - x][uq[1 - x]][2] = c;
                    }
                    C[1 - x][a - 1][b + 1][c] += ((a * C[x][a][b][c]) / N);
                }
                if(b)
                {
                    if(C[1 - x][a][b - 1][c + 1] == 0)
                    {
                        Q[1 - x][++uq[1 - x]][0] = a;
                        Q[1 - x][uq[1 - x]][1] = b - 1;
                        Q[1 - x][uq[1 - x]][2] = c + 1;
                    }
                    C[1 - x][a][b - 1][c + 1] += ((b * C[x][a][b][c]) / N);
                }
                if(c)
                {
                    if(C[1 - x][a + 1][b][c - 1] == 0)
                    {
                        Q[1 - x][++uq[1 - x]][0] = a + 1;
                        Q[1 - x][uq[1 - x]][1] = b;
                        Q[1 - x][uq[1 - x]][2] = c - 1;
                    }
                    C[1 - x][a + 1][b][c - 1] += ((c * C[x][a][b][c]) / N);
                }
            }

            pq[x]++;
        }

        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-10)
                break;
            Tot = Rez / pondere;
        }

        x = 1 - x;

        memset(C[1 - x], 0, sizeof(C[1 - x]));
        memset(Q[1 - x], 0, sizeof(Q[1 - x]));
        pq[x] = 1;
        uq[1 - x] = 0;
    }

    printf("%.6lf\n", Rez/pondere);


    return 0;
}