Cod sursa(job #1773596)

Utilizator mariusn01Marius Nicoli mariusn01 Data 7 octombrie 2016 23:23:05
Problema Car Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 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;
};

deque<elem> L[3];

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

elem make_elem(int i, int j, int d) {
    elem r;
    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]);
            //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;
    while (L[0].size() + L[1].size() + L[2].size() != 0) {
        while (L[p].size()) {
            elem crt = L[p].front();
            L[p].pop_front();
            if (V[crt.i][crt.j][crt.d] == 0) {
                V[crt.i][crt.j][crt.d] = step;
                if (crt.i == i2 && crt.j == j2) {
                    //fout<<step-1;
                    fprintf(fout, "%d", step-1);
                    return 0;
                }
                for (int k=-2;k<=2;k++) {
                    int iv = crt.i + di[ (crt.d + k + 8) & 7];
                    int jv = crt.j + dj[ (crt.d + k + 8) & 7];
                    if (a[iv][jv] != 0)
                        continue;
                    if (iv >= 1 && iv <= n && jv >= 1 && jv <= m && a[iv][jv] == 0 && V[iv][jv][(crt.d + k + 8) & 7] == 0)
                        L[ (p+modul(k)) % 3 ].push_back(make_elem(iv, jv, (crt.d + k + 8) & 7));
                }
            }
        }
        p = (p+1) % 3;
        step++;
    }
    fprintf(fout, "-1");
//    fout<<-1;
    return 0;
}