Cod sursa(job #1609824)

Utilizator algebristulFilip Berila algebristul Data 23 februarie 2016 02:33:19
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int Nmax = 550;
const double eps = 1e-3;
int n, m, N;
double a[Nmax][Nmax];
double D[23][23];
double x[Nmax];

inline int get(int x, int y) {
    return x * (N + 1) + y;
}

void build() {
    for (int i = 0; i <= get(N, N); i++) {
        for (int j = 0; j <= get(N, N) + 1; j++) {
            a[i][j] = 0;
        }
    }

    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N - i; j++) {
            if (i == 0 && j == N) {
                a[get(i, j)][get(i, j)] = 1;
                continue;
            }

            a[get(i, j)][get(i, j)] = -1;
            if (j > 0)
                a[get(i, j)][get(i, j - 1)] = 1. * j / N;

            if (i > 0 && j < N)
                a[get(i, j)][get(i - 1, j + 1)] = 1. * i / N;

            if (i < N)
                a[get(i, j)][get(i + 1, j)] = 1. * (N - i - j) / N;

            a[get(i, j)][get(N, N) + 1] = -1;
        }
    }
}

void gauss() {
    int i = get(0, 0), j = get(0, 0);
    int n = get(N, N);

    while (i <= n && j <= n) {
        int k;

        for (k = i; k <= n; k++) {
            if (!(a[k][j] > -eps && a[k][j] < eps))
                break;
        }

        if (k == n+1) {
            j++;
            continue;
        }

        if (k != i) {
            for (int t = 0; t <= n + 1; t++) {
                swap(a[i][t], a[k][t]);
            }
        }

        for (int l = j + 1; l <= n + 1; l++) {
            a[i][l] = a[i][l] / a[i][j];
        }

        a[i][j] = 1;

        for (int lin = i + 1; lin <= n; lin++) {
            for (int col = j + 1; col <= n + 1; col++) {
                a[lin][col] -= a[lin][j] * a[i][col];
            }
            a[lin][j] = 0;
        }

        i++;
        j++;
    }

    for (i = n; i >= 0; i--) {
        for (j = 0; j <= n; j++) {
            if (a[i][j] < -eps || a[i][j] > eps) {
                break;
            }
        }

        x[j] = a[i][n + 1];
        for (int k = j + 1; k <= n; k++)
            x[j] -= x[k] * a[i][k];
    }
}

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

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

    build();
    gauss();

    printf("%.6lf\n", x[get(0, 0)]);

    return 0;
}