Cod sursa(job #1773631)

Utilizator mariusn01Marius Nicoli mariusn01 Data 7 octombrie 2016 23:57:42
Problema Car Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <cstdio>
#include <queue>
#define DIM 503

int di[] = {-1,-1,0,1,1, 1, 0,-1};
int dj[] = { 0, 1,1,1,0,-1,-1,-1};
using namespace std;

int V[DIM][DIM][8];
int a[DIM][DIM];

struct elem {
    int i;
    int j;
    int d;
};
elem r;
deque<elem> L[3];

int n, m, i1, j1, i2, j2;

elem make_elem(int i, int j, int d) {
    r.i = i;
    r.j = j;
    r.d = d;
    return r;
}

inline int modul(int x) {
    return ( x > 0 ? x : -x );
}

int main () {
    FILE * fin = fopen ("car.in", "r");
    FILE *fout = fopen ("car.out", "w");
    fscanf(fin,"%d %d %d %d %d %d", &n, &m, &i1, &j1, &i2, &j2);
    //fin>>n>>m;
    //fin>>i1>>j1>>i2>>j2;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++) {
            fscanf(fin, "%d", &a[i][j]);
            a[i][0] = a[i][m+1] = 1;
        }
    for (register int i=0;i<=m+1;i++)
        a[0][i] = a[n+1][i] = 1;
            //fin>>a[i][j];
    for (int i=0;i<8;i++) {
        L[0].push_back(make_elem(i1, j1, i));
    }

    int p = 0;
    int step = 1;
    register int iv, jv, nextd, ci, cj, cd;

    while (L[0].size() + L[1].size() + L[2].size()) {
        while (L[p].size()) {
            elem crt = L[p].front();
            ci = crt.i;
            cj = crt.j;
            cd = crt.d;
            L[p].pop_front();
            if (!V[ci][cj][cd]) {
                V[ci][cj][cd] = step;
                if (ci == i2 && cj == j2) {
                    //fout<<step-1;
                    fprintf(fout, "%d", step-1);
                    return 0;
                }
                for (register int k=-1;k<=1;k++) {
                    nextd = cd + k;
                    nextd &= 7;

                    if (k == 0) {
                        iv = ci + di[ nextd ];
                        jv = cj + dj[ nextd ];
                    } else {
                        iv = ci;
                        jv = cj;
                    }
                    if (a[iv][jv] != 0)
                        continue;
                    if (V[iv][jv][nextd] == 0)
                        L[ (p+modul(k)) & 1 ].push_back(make_elem(iv, jv, nextd));
                }
            }
        }
        p = 1-p;
        step++;
    }
    fprintf(fout, "-1");
//    fout<<-1;
    return 0;
}