Cod sursa(job #907737)

Utilizator darrenRares Buhai darren Data 8 martie 2013 11:40:32
Problema Minesweeper Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <fstream>
#include <iomanip>
#include <algorithm>

using namespace std;

const double eps = 0.0001;

int N, M;
int where[22][22], isnow;
double A[502][502], X[502];

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

    fin >> N >> M;
    N *= M;

    for (int i = 0; i <= N; ++i)
        for (int j = 0; i + j <= N; ++j)
            where[i][j] = ++isnow;

    for (int i = 0; i <= N; ++i)
        for (int j = 0; i + j <= N; ++j)
        {
            A[where[i][j]][where[i][j]] -= 1.0;

            int a = i, b = j, c = N - (a + b);

            if (c == N) continue;

            if (a != 0) A[where[i][j]][where[i - 1][j + 1]] += 1.0 * a / (a + b + c);
            if (b != 0) A[where[i][j]][where[i][j - 1]] += 1.0 * b / (a + b + c);
            if (c != 0) A[where[i][j]][where[i + 1][j]] += 1.0 * c / (a + b + c);

            A[where[i][j]][isnow + 1] -= 1.0;
        }

    for (int i = 1, j = 1; i <= isnow && j <= isnow; ++i, ++j)
    {
        int findnow;
        for (findnow = i; findnow <= isnow && !(A[findnow][j] < -eps || A[findnow][j] > eps); ++findnow);
        if (findnow == isnow + 1)
        {
            --i;
            continue;
        }

        for (int k = 1; k <= isnow + 1; ++k)
            swap(A[i][k], A[findnow][k]);

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

        for (int k = i + 1; k <= isnow; ++k)
        {
            rednow = A[k][j];
            for (int l = 1; l <= isnow + 1; ++l)
                A[k][l] -= A[i][l] * rednow;
        }
    }

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

    fout << fixed << setprecision(8) << X[where[N][0]] << '\n';

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