Cod sursa(job #1522638)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 11 noiembrie 2015 21:17:52
Problema Minesweeper Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <bits/stdc++.h>

#define INF (1 << 30)
#define LLINF (1LL << 62)
#define mod 666013
#define eps 0.000001

using namespace std;

int n, m, i, j, k, keye, x, y, z, st;
double sol, coef;
double a[505][505];
char ok[505];

int key(int a, int b, int c)
{
    return (b * (n + 1) + a);
}

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

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

    for(i = 0; i <= n; i++)
        for(j = 0; i + j <= n; j++)
        {
            x = i;
            y = j;
            z = n - i - j;

            keye = key(x, y, z);
            st = 0;

            ok[keye] = 1;

            if(keye == 0)
            {
                a[keye][0] = 1;
                a[keye][m] = 0;
                continue;
            }

            if(x)
            {
                a[keye][key(x - 1, y + 1, z)] = (double)x / n;
                a[keye][m] -= (double)x / n;
            }
            if(y)
            {
                a[keye][key(x, y - 1, z + 1)] = (double)y / n;
                a[keye][m] -= (double)y / n;
            }
            if(z)
            {
                a[keye][key(x + 1, y, z - 1)] = (double)z / n;
                a[keye][m] -= (double)z / n;
            }

            a[keye][keye] = -1;
            a[keye][m] = -1;
        }

    for(i = 0; i < m; i++)
    {
        if(!ok[i])
            continue;

        st = i;

        for(j = 0; j < m; j++)
        {
            if(i == j)
                continue;

            coef = a[j][st] / a[i][st];
            for(k = 0; k <= m; k++)
                a[j][k] = a[j][k] - a[i][k] * coef;
        }
    }

    //sol = (double)a[0][m] / (double)a[0][0];
    //printf("%.6f\n", sol);

    sol = (double)a[n][m] / (double)a[n][n];
    printf("%.6f\n", sol);

    //sol = (double)a[n * (n + 1)][m] / (double)a[n * (n + 1)][n * (n + 1)];
    //printf("%.6f", sol);

    return 0;
}