Cod sursa(job #1195108)

Utilizator smaraldaSmaranda Dinu smaralda Data 6 iunie 2014 10:29:23
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

const int NMAX = 22, EQMAX = 600;

int n, m, cnt, prod, code[NMAX + 5][NMAX + 5];
double coef[EQMAX + 5][EQMAX + 5];

void swapLines (int a, int b) {
    if(a == b)
        return;

    int j;
    for(j = 1; j <= cnt + 1; ++ j)
        swap(coef[a][j], coef[b][j]);
}

void gauss () {
    int i, j, k;
    double alpha;

    for(j = 1; j <= cnt; ++ j) {
        for(i = j; i <= cnt; ++ i)
            if(coef[i][j]) {
                swapLines(i, j);
                break;
            }

        for(i = 1; i <= cnt; ++ i)
            if(i != j) {
                alpha = coef[i][j] / coef[j][j];

                for(k = 1; k <= cnt + 1; ++ k)
                    coef[i][k] -= alpha * coef[j][k];
            }
    }
}

int main() {
    freopen("minesweeper.in", "r", stdin);
    freopen("minesweeper.out", "w", stdout);
    int i, j, a, b, prod;

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

    cnt = 0 ;
    for(i = 0; i <= prod; ++ i)
        for(j = 0; j <= prod - i; ++ j)
            code[i][j] = ++ cnt;

    for(a = 0; a <= prod; ++ a)
        for(b = 0; b <= prod - a; ++ b) {
            coef[code[a][b]][code[a - 1][b + 1]] = (double)a / prod;
            coef[code[a][b]][code[a][b - 1]] = (double)b / prod;
            coef[code[a][b]][code[a + 1][b]] = ((double)prod - a - b) / (double)prod;
            coef[code[a][b]][code[a][b]] = coef[code[a][b]][cnt + 1] = -1;
        }

    for(j = 1; j <= cnt + 1; ++ j)
        coef[code[0][0]][j] = 0;
    coef[code[0][0]][code[0][0]] = 1;

    gauss();

    printf("%lf", coef[cnt][cnt + 1] / coef[cnt][cnt]);
    return 0;
}