Cod sursa(job #1703476)

Utilizator akaprosAna Kapros akapros Data 16 mai 2016 23:26:05
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.92 kb
#include <bits/stdc++.h>
#define maxN 25
#define e 0.0000000001
using namespace std;
int n, m, N, M, st[maxN][maxN];
double a[maxN * maxN][maxN * maxN], x[maxN * maxN];

void Swap(double &x, double &y)
{
    double aux;
    aux = x;
    x = y;
    y = aux;
}

void read()
{
    freopen("minesweeper.in", "r", stdin);
    scanf("%d %d", &n, &m);
    n = n * m;
}
void Gauss()
{
    int i = 0, j = 0;
    while (i <= N && j <= M)
    {
        int x, y;
        for (x = i; x <= N; ++ x)
            if (a[x][j] < -e || a[x][j] > e)
                break;
        if (x == N + 1)
        {
            ++ j;
            continue;
        }
        if (x != i)
            for (y = 0; y <= M + 1; ++ y)
                Swap(a[x][y], a[i][y]);

        for (y = j + 1; y <= M + 1; ++ y)
            a[i][y] = (double)(a[i][y] / a[i][j]);
        a[i][j] = 1.00000000000;

        for (y = i + 1; y <= N; ++ y)
        {
            int c;
            for (c = j + 1; c <= M + 1; ++ c)
                a[y][c] -= a[y][j] * a[i][c];
            a[y][j] = 0.0000000000;
        }
        ++ i;
        ++ j;
    }
}
void Coef()
{
    int i, j, idx;
    x[st[0][0]] = 0.00;
    for (i = N; i >= 0; -- i)
        for (j = 0; j <= M + 1; ++ j)
            if (a[i][j] < -e || a[i][j] > e)
            {
                if (j == M + 1)
                {
                    x[0] = 0;
                    return;
                }

                x[j] = a[i][M + 1];
                for (idx = j + 1; idx <= M; ++ idx)
                    x[j] -= a[i][idx] * x[idx];
                break;
            }
}
void solve()
{
    int i, j;

    N = M = 0;
    for (i = 0; i <= n; ++ i)
        for (j = 0; i + j <= n; ++ j)
            st[i][j] = N ++;
    M = N;
    for (i = 0; i <= n; ++ i)
        for (j = 0; i + j <= n; ++ j)
        {
            int x = st[i][j], y;
            if (x == 0)
                {
                    a[x][x] = 1.000;
                    continue;
                }

            if (i > 0)
            {
                y = st[i - 1][j + 1];
                a[x][y] = (double)(1.00 * i / n);
                //a[x][N + 1] -= (double)(1.00 * i / n);
            }
            if (j > 0)
            {
                y = st[i][j - 1];
                a[x][y] = (double)(1.00 * j / n);
                //a[x][N + 1] -= (double)(1.00 * j / n);
            }
            if (n - j - i > 0)
            {
                y = st[i + 1][j];
                a[x][y] = (double)(1.00 * (n - j - i) / n);
                //a[x][N + 1] -= (double)(1.00 * (n - j - i) / n);
            }
            a[x][x] = -1.000;
            a[x][N + 1] = -1.0000;
        }

    Gauss();
    Coef();
}
void write()
{
    freopen("minesweeper.out", "w", stdout);
    printf("%.6lf", x[st[n][0]]);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}