Cod sursa(job #1443679)

Utilizator GeiGeiGeorge Cioroiu GeiGei Data 28 mai 2015 14:10:33
Problema Asmax Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
//0074
#include <cstdio>

long dp[25][105][105];

int main() {
    FILE* fi = fopen("homm.in", "rt");
    FILE* fo = fopen("homm.out", "wt");

    int m, n, k;
    fscanf(fi, "%d%d%d", &m, &n, &k);

    for (int i = 0; i <= m + 1; i++) {
        for (int l = 0; l <= k; l++) {
            dp[l][i][0] = dp[l][i][n + 1] = -1;
        }
    }

    for (int j = 0; j <= n + 1; j++) {
        for (int l = 0; l <= k; l++) {
            dp[l][0][j] = dp[l][m + 1][j] = -1;
        }
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            long aux;
            fscanf(fi, "%ld", &aux);
            aux = (aux == 0) ? 0 : -1;
            for (int l = 0; l <= k; l++)
                dp[l][i][j] = aux;
        }
    }

    int x0, y0, x1, y1;
    fscanf(fi, "%d%d%d%d", &x0, &y0, &x1, &y1);

    dp[0][x0][y0] = 1;
    long ans = dp[0][x1][y1];

    for (int l = 0; l < k; l++) {
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (dp[l][i][j] > 0) {
                    if (dp[l][i - 1][j] != -1) {
                        dp[l + 1][i - 1][j] += dp[l][i][j];
                    }
                    if (dp[l][i + 1][j] != -1) {
                        dp[l + 1][i + 1][j] += dp[l][i][j];
                    }
                    if (dp[l][i][j - 1] != -1) {
                        dp[l + 1][i][j - 1] += dp[l][i][j];
                    }
                    if (dp[l][i][j + 1] != -1) {
                        dp[l + 1][i][j + 1] += dp[l][i][j];
                    }
                }
            }
        }
        ans += dp[l + 1][x1][y1];
    }

    fprintf(fo, "%ld", ans);

    return 0;
}