Cod sursa(job #1304734)

Utilizator andreiiiiPopa Andrei andreiiii Data 29 decembrie 2014 11:13:35
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cmath>

using namespace std;

const int Nmax = 25, Mmax = 300;
const double eps = 1e-10;

int Key[Nmax][Nmax];
double *A[Mmax], __A[Mmax][Mmax], X[Mmax];

void Gauss(int M, int N) {
    for (int i = 1, j = 1; i <= N && j <= M; ++i, ++j) {
        int k;
        for (k = i; k <= N && abs(A[k][j]) < eps; ++k);

        if (k == N + 1) {
            --i;
            continue;
        }

        if (i != k) swap(A[i], A[k]);

        for (int k = j + 1; k <= M + 1; ++k)
            A[i][k] /= A[i][j];
        A[i][j] = 1;

        for (int k = i + 1; k <= N; ++k) {
            for (int p = j + 1; p <= M + 1; ++p)
                A[k][p] -= A[i][p] * A[k][j];
            A[k][j] = 0;
        }
    }

    for (int i = N; i > 0; --i) {
        for (int j = 1; j <= M + 1; ++j) {
            if (abs(A[i][j]) > eps) {
                X[j] = A[i][M + 1];
                for (int k = j + 1; k <= M; ++k)
                    X[j] -= A[i][k] * X[k];
                break;
            }
        }
    }
}

int main()
{
    ifstream fin("minesweeper.in");
    ofstream fout("minesweeper.out");

    int N, M;
    fin >> N >> M;

    N *= M;

    int cnt = 0;
    for (int i = 0; i <= N; ++i)
        for (int j = 0; j <= N && i + j <= N; ++j)
            Key[i][j] = ++cnt;

    M = 0;
    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= N && i + j <= N; ++j) {
            if (i == 0 && j == 0) continue;
            ++M;
            A[M] = __A[M];

            A[M][Key[i][j]] = 1;
            if (i > 0)
                A[M][Key[i - 1][j + 1]] = (double) -i / N;
            if (j > 0 && (j - 1 != 0 || i != 0))
                A[M][Key[i][j - 1]] = (double) -j / N;
            if (N - i - j > 0)
                A[M][Key[i + 1][j]] = (double) -(N - i - j) / N;
            A[M][cnt + 1] = 1;
        }
    }

    Gauss(cnt, M);

    fout << setprecision(6) << fixed;
    fout << X[Key[N][0]] << '\n';

    fin.close();
    fout.close();
}