Cod sursa(job #637675)

Utilizator savimSerban Andrei Stan savim Data 20 noiembrie 2011 15:54:01
Problema Minesweeper Scor 60
Compilator cpp Status done
Runda .com 2011 Marime 1.17 kb
#include <cstdio>
#include <cstring>

using namespace std;

#define MAX_N 25

int x, y, n;

double c[2][MAX_N][MAX_N];

void solve() {
    memset(c, 0, sizeof(c));

    c[0][n][0] = 1;

    double ans = 0;

    int l = 0;
    for (int steps = 1; steps <= 5000000; steps++) {
        for (int i = 0; i <= n; i++)
            for (int j = 0; i + j <= n; j++) {
                if (!(i == 0 && j == 0)) {
                    c[1 ^ l][i - 1][j + 1] += c[l][i][j] * i / n;
                    c[1 ^ l][i][j - 1] += c[l][i][j] * j / n;
                    c[1 ^ l][i + 1][j] += c[l][i][j] * (n - i - j) / n;
                }
            
                c[l][i][j] = 0;
            }
        
        l ^= 1;

        ans += c[l][0][0] * steps;
    }

    printf("%lf\n", ans);
}

int main() {

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

    scanf("%d %d", &x, &y); n = x * y;

    double A[] = {2.000000, 9.000000, 28.928571, 86.439560, 255.157027, 754.871822, 2242.547143, 6683.817095, 19963.922320, 59712.121698,
                  178754.843365, 534939.556737};

    if (n <= 12)
        printf("%f\n", A[n - 1]);
    else
        solve();

    return 0;
}