Cod sursa(job #2034536)

Utilizator mihai.alphamihai craciun mihai.alpha Data 7 octombrie 2017 22:53:19
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <cstdio>
#include <cstdlib>
#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 dp;
};

int a[MAXN + 1][MAXN + 1];
int dp[MAXN + 1][MAXN + 1];
int si, sj, fi, fj;
std::queue <at1> q;
#define inf (int)1e9
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 who[3][3];

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]);
            dp[i][j] = inf;
        }
    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[si + dx[i]][sj + dy[i]] = 0;
    }
    dp[si][sj] = 0;
    who[0][1] = 0;
    who[0][2] = 1;
    who[1][2] = 2;
    who[2][2] = 3;
    who[2][1] = 4;
    who[2][0] = 5;
    who[1][0] = 6;
    who[0][0] = 7;
    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;
        if(fi == eu.i && fj == eu.j)  {
            fprintf(fout, "%d", dp[fi][fj]);
            return 0;
        }
        int whi = nod.dir;
        for(int i = 0;i < 8;i++)  {
            at vec;
            vec.i = eu.i + dx[i];
            vec.j = eu.j + dy[i];
            if(a[vec.i][vec.j])
                continue;
            if(dp[vec.i][vec.j] > nod.dp + cost[whi][i])  {
                dp[vec.i][vec.j] = nod.dp + cost[whi][i];
                    q.push({vec, i, dp[vec.i][vec.j]});
            }
        }
    }
        fprintf(fout, "-1");
    fclose(fin);
    fclose(fout);
}