Cod sursa(job #2034581)

Utilizator mihai.alphamihai craciun mihai.alpha Data 8 octombrie 2017 00:29:05
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <deque>

FILE *fin, *fout;

int N, M;

#define MAXN 504

struct at  {
    int i, j;
};

struct at1  {
    at de;
    int dir;
};

int a[MAXN + 1][MAXN + 1];
int dp[9][MAXN + 1][MAXN + 1];
int si, sj, fi, fj;
std::deque <at1> dq;

#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++)  {
        dq.push_back({{si, sj}, i});
    }
    for(int i = 0;i < 8;i++)
        dp[i][si][sj] = 0;
    while(!dq.empty())  {
        at1 nod = dq.front();
        dq.pop_front();
        at eu = nod.de;
        if(eu.i == fi && eu.j == fj)  {
            int val = inf;
            for(int i = 0;i < 8;i++)
                val = std::min(dp[i][fi][fj], val);
            fprintf(fout, "%d", val);
            return 0;
        }
        at vec;
        int whi = nod.dir;
        int i = whi;
        vec.i = eu.i + dx[i];
        vec.j = eu.j + dy[i];
        if(a[vec.i][vec.j] == 0)  {
            if(dp[i][vec.i][vec.j] > dp[whi][eu.i][eu.j])  {
                dp[i][vec.i][vec.j] = dp[whi][eu.i][eu.j];
                dq.push_front({vec, i});
            }
        }


        i = (whi + 1) % 8;
        vec.i = eu.i;
        vec.j = eu.j;
        if(a[vec.i][vec.j] == 0 && dp[i][vec.i][vec.j] > dp[whi][eu.i][eu.j] + 1)  {
            dp[i][vec.i][vec.j] = dp[whi][eu.i][eu.j] + 1;
            dq.push_back({vec, i});
        }


        i = (whi + 7) % 8;
        vec.i = eu.i;
        vec.j = eu.j;
        if(a[vec.i][vec.j] == 0 && dp[i][vec.i][vec.j] > dp[whi][eu.i][eu.j] + 1)  {
            dp[i][vec.i][vec.j] = dp[whi][eu.i][eu.j] + 1;
            dq.push_back({vec, i});
        }


    }
    fprintf(fout, "%d", -1);
    fclose(fin);
    fclose(fout);
}