Cod sursa(job #640861)

Utilizator spatarelDan-Constantin Spatarel spatarel Data 26 noiembrie 2011 16:59:47
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda minesweeper2 Marime 5.19 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int N, M;

long double SOL;

void gauss_swap_rows(int i, int j, int N, long double** A, long double* B, int* ID) {
    if (i != j) {
        int k;
        long double tmp;
        tmp = B[i];
        B[i] = B[j];
        B[j] = tmp;
        ID[i] ^= ID[j];
        ID[j] ^= ID[i];
        ID[i] ^= ID[j];
        for (k = i; k < N; ++k) {
            tmp = A[i][k];
            A[i][k] = A[j][k];
            A[j][k] = tmp;
        }
    }
}

void gauss_swap_columns(int i, int j, int N, long double** A, long double* B, int* ID) {
    if (i != j) {
        int k;
        long double tmp;
        //ID[i] ^= ID[j];
        //ID[j] ^= ID[i];
        //ID[i] ^= ID[j];
        for (k = 0; k < N; ++k) {
            tmp = A[k][i];
            A[k][i] = A[k][j];
            A[k][j] = tmp;
        }
    }
}

void gauss_unswap(int N, long double *B, int *ID) {
    int i;
    long double* tmp = (long double*)(malloc(N * sizeof(long double)));
    for (i = 0; i < N; ++i) {
        tmp[ID[i]] = B[i];
    }
    for (i = 0; i < N; ++i) {
        B[i] = tmp[i];
    }
    free(tmp);
}

void dump(int N, long double** A, long double* B) {
    int i, j;
    for (i = 0; i < N; ++i) {
        for (j = 0; j < N; ++j) {
            printf("%.2Lf ", A[i][j]);
        }
        printf("| %.2Lf\n", B[i]);
    }
    printf("----------------------------------------------------\n");
}

void gauss(int N, long double** A, long double* B) {
    int i, j, k;
    long double max;
    int posA, posB;
    double r;
    //dump(N, A, B);
    int* ID = (int*)(malloc(N * sizeof(int)));
    for (i = 0; i < N; ++i) {
        ID[i] = i;
    }
    for (i = 0; i < N; ++i) {
        max = fabs(A[i][i]);
        posA = i;
        posB = i;
        for (j = i; j < N; ++j) {
            for (k = i; k < N; ++k) {
                if (max < fabs(A[j][k])) {
                    max = fabs(A[j][k]);
                    posA = j;
                    posB = k;
                }
            }
        }
        gauss_swap_rows(i, posA, N, A, B, ID);
        gauss_swap_columns(i, posB, N, A, B, ID);
        //dump(N, A, B);
        for (j = i + 1; j < N; ++j) {
            r = A[j][i] / A[i][i];
            B[j] -= r * B[i];
            for(k = N; k >= i; --k) {
                A[j][k] -= r * A[i][k];
            }
        }
        B[i] /= A[i][i];
        for(k = N; k >= i; --k) {
            A[i][k] /= A[i][i];
        }
    }
    for (i = N - 1; i >= 0; --i) {
        for (j = i - 1; j >= 0; --j) {
            B[j] -= (A[j][i] / A[i][i]) * B[i];
            A[j][i] = 0;
        }
    }
    //dump(N, A, B);
    gauss_unswap(N, B, ID);
    //dump(N, A, B);
    free(ID);
}

long double** gauss_alloc_a(int N) {
    int i, j;
    long double** A;
    A = (long double**)(malloc(N * sizeof(long double*)));
    for (i = 0; i < N; ++i) {
        A[i] = (long double*)(malloc(N * sizeof(long double)));
        for (j = 0; j < N; ++j) {
            A[i][j] = 0;
        }
    }
    return A;
}

long double* gauss_alloc_b(int N) {
    return (long double*)(malloc(N * sizeof(long double)));
}

int ID[23][23];

int main(void) {
    int i, j, k;
    FILE *f,*ff;

    // citirea datelor
    f = fopen("minesweeper.in", "r");
    fscanf(f, "%d %d", &N, &M);
    fclose(f);

    // calcularea solutiei
    N *= M;
    int gaussN;
    for (i = 0, gaussN = 0; i <= N; ++i) {
        for (j = 0; i + j <= N; ++j, ++gaussN) {
            ID[i][j] = gaussN;
        }
    }
    long double** A1 = gauss_alloc_a(gaussN);
    long double* B1 = gauss_alloc_b(gaussN);

    for (i = 0, k = 0; i <= N; ++i) {
        for (j = 0; i + j <= N; ++j, ++k) {
            k = N - (i + j);
            if (i + 1 <= N && j - 1 >= 0) {
                A1[ID[i][j]][ID[i + 1][j - 1]] = -(long double)(i + 1) / N;
            }
            if (j + 1 <= N) {
                A1[ID[i][j]][ID[i][j + 1]] = -(long double)(j + 1) / N;
            }
            if (i - 1 >= 0) {
                A1[ID[i][j]][ID[i - 1][j]] = -(long double)(k + 1) / N;
            }

            A1[ID[i][j]][ID[0][0]] = 0;
            A1[ID[i][j]][ID[i][j]] = 1;
        }
    }
    B1[ID[N][0]] = 1;
    gauss(gaussN, A1, B1);
    B1[ID[0][0]] = 0;

    long double** A2 = gauss_alloc_a(gaussN);
    long double* B2 = gauss_alloc_b(gaussN);

    for (i = 0, k = 0; i <= N; ++i) {
        for (j = 0; i + j <= N; ++j, ++k) {
            k = N - (i + j);
            if (i + 1 <= N && j - 1 >= 0) {
                A2[ID[i][j]][ID[i + 1][j - 1]] = -(long double)(i + 1) / N;
                B2[ID[i][j]] += B1[ID[i + 1][j - 1]] * (long double)(i + 1) / N;
            }
            if (j + 1 <= N) {
                A2[ID[i][j]][ID[i][j + 1]] = -(long double)(j + 1) / N;
                B2[ID[i][j]] += B1[ID[i][j + 1]] * (long double)(j + 1) / N;
            }
            if (i - 1 >= 0) {
                A2[ID[i][j]][ID[i - 1][j]] = -(long double)(k + 1) / N;
                B2[ID[i][j]] += B1[ID[i - 1][j]] * (long double)(k + 1) / N;
            }

            A2[ID[i][j]][ID[0][0]] = 0;
            A2[ID[i][j]][ID[i][j]] = 1;
        }
    }
    gauss(gaussN, A2, B2);

    // afisarea solutiei
    ff = fopen("minesweeper.out", "w");
    fprintf(ff, "%Lf\n", B2[ID[0][0]]);
    fclose(ff);
    return 0;
}