Cod sursa(job #1250273)

Utilizator geniucosOncescu Costin geniucos Data 27 octombrie 2014 22:44:47
Problema Minesweeper Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include<cstdio>

using namespace std;

int nr, n, m, X, cod[30][30];
double eps, A[500][500];

double Get (int p)
{
    return A[p][nr+1] / A[p][p];
}

void afis ()
{
    for (int i=1; i<=nr; i++, printf("\n"))
        for (int j=1; j<=nr+1; j++)
            printf ("%.5lf ", A[i][j]);
}

int main()
{
freopen ("minesweeper.in", "r", stdin);
freopen ("minesweeper.out", "w", stdout);
scanf ("%d %d", &n, &m);
X = n * m;
for (int i=0; i <= X; i++)
    for (int j=0; i+j <=X; j++)
        cod[i][j] = ++nr;

for (int i=0; i<=X; i++)
    for (int j=0; i+j <=X; j++)
    {
        if (i==0 && j==0)
        {
            A[cod[i][j]][cod[i][j]] = 1.0;
            continue;
        }
        A[cod[i][j]][cod[i][j]] = 1.0;
        if (i) A[cod[i][j]][cod[i-1][j+1]] = (double) -i/X;
        if (j) A[cod[i][j]][cod[i][j-1]] = (double) -j/X;
        A[cod[i][j]][cod[i+1][j]] = (double) -(X-i-j)/X;
        A[cod[i][j]][nr+1] = 1.0;
    }

eps = 0.000000001;
for (int i=1; i<=nr; i++)
{
    int p = 0;
    for (int j=1; j<=nr+1; j++)
        if (A[i][j] < -eps || A[i][j] > eps)
        {
            p = j;
            break;
        }
    if (p == 0) continue;
    for (int j=1; j<=nr; j++)
        if (i != j && (A[j][p] > eps || A[j][p] < -eps))
        {
            double rap = A[j][p] / A[i][p];
            for (int k=1; k<=nr+1; k++)
                A[j][k] = (double) A[j][k] - A[i][k] * rap;
        }
    //afis();
    //printf ("\n\n");
}

printf ("%.6lf\n", Get (cod[X][0]));

return 0;
}