Cod sursa(job #1563010)

Utilizator akaprosAna Kapros akapros Data 5 ianuarie 2016 17:14:44
Problema Car Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <bits/stdc++.h>
#define maxN 502
#define inf 1000000000
#define maxD 8
using namespace std;
int n, m, sol, si, sj, fi, fj, cost[maxN][maxN][maxD];
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, -1, -1, -1, 0, 1, 1, 1};
int a[maxN][maxN], c[maxD][maxD];
int ok(int x, int y)
{
    if (x < 1 || y < 1 || x > n || y > m || a[x][y] == 1)
        return 0;
    return 1;
}
void cost_dir()
{
    int i, j;
    for (i = 0; i < maxD - 1; ++ i)
        for (j = i + 1; j < maxD; ++ j)
        {
            if (j - i <= 4)
                c[i][j] = c[j][i] = j - i;
            else
                c[i][j] = c[j][i] = j - i - 4;
        }
}
void read()
{
    int i, j, d;
    freopen("car.in", "r", stdin);
    scanf("%d %d", &n, &m);
    scanf("%d %d %d %d", &si, &sj, &fi, &fj);
    for (i = 1; i <= n; ++ i)
        for (j = 1; j <= m; ++ j)
        {
            scanf("%d", &a[i][j]);
            for (d = 0; d < 8; ++ d)
                if (i != si || j != sj)
                    cost[i][j][d] = inf;
        }

}
void dfs(int x, int y, int d)
{
    int k;
    for (k = 0; k < 8; ++ k)
        if (ok(x + dx[k], y + dy[k]) && cost[x + dx[k]][y + dy[k]][k] > cost[x][y][d] + c[d][k])
        {
            cost[x + dx[k]][y + dy[k]][k] = cost[x][y][d] + c[d][k];
            dfs(x + dx[k], y + dy[k], k);
        }
}
void solve()
{
    int d;
    cost_dir();
    sol = inf;
    for (d = 0; d < 8; ++ d)
        dfs(si, sj, d);
    for (d = 0; d < 8; ++ d)
        if (sol > cost[fi][fj][d])
            sol = cost[fi][fj][d];
}
void write()
{
    freopen("car.out", "w", stdout);
    if (sol == inf)
        printf("-1\n");
    else
        printf("%d\n", sol);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}