Cod sursa(job #2034556)

Utilizator mihai.alphamihai craciun mihai.alpha Data 7 octombrie 2017 23:14:03
Problema Car Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>

FILE *fin, *fout;

int N, M;

#define MAXN 500

struct at  {
    int i, j;
};

struct at1  {
    at de;
    int dir;
};

int a[MAXN + 1][MAXN + 1];
int dp[8][MAXN + 1][MAXN + 1];
int si, sj, fi, fj;
std::queue <at1> q;

#define INF 0x3f3f3f3f
#define inf 1061109567

int cost[8][8];

const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

int main()  {
    fin = fopen("car.in", "r");
    fout = fopen("car.out", "w");
    fscanf(fin, "%d%d", &N, &M);
    fscanf(fin, "%d%d%d%d", &si, &sj, &fi, &fj);
    for(int i = 1;i <= N;i++)
        for(int j = 1;j <= M;j++)  {
            fscanf(fin, "%d", &a[i][j]);
        }
    memset(dp, INF, sizeof dp);
    for(int i = 0;i <= N + 1;i++)
        a[i][0] = a[i][M + 1] = 1;
    for(int i = 0;i <= M + 1;i++)
        a[0][i] = a[N + 1][i] = 1;
    for(int i = 0;i < 8;i++)  {
        if(a[si + dx[i]][sj + dy[i]])
            continue;
        q.push({{si + dx[i], sj + dy[i]}, i});
        dp[i][si + dx[i]][sj + dy[i]] = 0;
    }
    for(int i = 0;i < 8;i++)
        dp[i][si][sj] = 0;
    for(int i = 0;i < 8;i++)  {
        cost[i][i] = 0;
        for(int j = 0;j < 8;j++)  {
            int dif = abs(i - j);
            if(i == j)
                continue;
            cost[i][j] = std::min(dif, 8 - dif);
        }
    }
    while(!q.empty())  {
        at1 nod = q.front();
        q.pop();
        at eu = nod.de;
        int whi = nod.dir;
        for(int i = 0;i < 8;i++)  {
            if(cost[i][whi] >= 3)
                continue;
            at vec;
            vec.i = eu.i + dx[i];
            vec.j = eu.j + dy[i];
            if(a[vec.i][vec.j])
                continue;
            if(dp[i][vec.i][vec.j] > dp[whi][eu.i][eu.j] + cost[whi][i])  {
                dp[i][vec.i][vec.j] = dp[whi][eu.i][eu.j] + cost[whi][i];
                    q.push({vec, i});
            }
        }
    }
    int val = inf;
    for(int i = 0;i < 8;i++)
        val = std::min(dp[i][fi][fj], val);
    if(val == inf)
        fprintf(fout, "-1");
    else
        fprintf(fout, "%d", val);
    fclose(fin);
    fclose(fout);
}