Cod sursa(job #1161856)

Utilizator poptibiPop Tiberiu poptibi Data 31 martie 2014 15:04:56
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;

const int NMAX = 25, EMAX = 600;
const double EPS = 1e-6;

int N, M, C[NMAX][NMAX], K, E;
double A[EMAX][EMAX];

void DoGauss()
{
    int Ec = 2, Nec = 1;
    while(Ec <= E && Nec <= E)
    {
        int i;
        for(i = Ec; i <= E; ++ i)
            if(fabs(A[i][Nec]) > EPS)
                break;

        if(i == E + 1)
        {
            Nec ++;
            continue;
        }

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

        for(int i = 1; i <= E; ++ i)
            if(i != Ec)
            {
                double R = A[i][Nec] / A[Ec][Nec];
                for(int j = Nec; j <= E + 1; ++ j)
                    A[i][j] -= A[Ec][j] * R;
            }

        Ec ++;
        Nec ++;
    }

    printf("%.6lf\n", A[E][E + 1] / A[E][E]);
}

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

    scanf("%i %i", &N, &M);
    for(int i = 0; i <= N * M; ++ i)
        for(int j = 0; i + j <= N * M; ++ j)
            C[i][j] = ++ E;

    for(int i = 0; i <= N * M; ++ i)
        for(int j = 0; i + j <= N * M; ++ j)
        {
            A[ C[i][j] ][ C[i - 1][j + 1] ] = 1.0 * i / (N * M);
            A[ C[i][j] ][ C[i][j - 1] ] = 1.0 * j / (N * M);
            A[ C[i][j] ][ C[i + 1][j] ] = 1.0 * (N * M - i - j) / (N * M);
            A[ C[i][j] ][ C[i][j] ] = -1.0;
            A[ C[i][j] ][ E + 1] = -1.0;
        }

    for(int i = 1; i <= E + 1; ++ i)
        A[ C[0][0] ][i] = A[i][ C[0][0] ] = 0;

    DoGauss();
}