Cod sursa(job #1773615)

Utilizator mariusn01Marius Nicoli mariusn01 Data 7 octombrie 2016 23:38:48
Problema Car Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 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]) {
                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 (register int k=-1;k<=1;k++) {
                    register int nextd = crt.d + k;
                    if (nextd == -1)
                        nextd = 7;
                    if (nextd == 8)
                        nextd = 0;
                    register int iv, jv;
                    if (k == 0) {
                        iv = crt.i + di[ nextd ];
                        jv = crt.j + dj[ nextd ];
                    } else {
                        iv = crt.i;
                        jv = crt.j;
                    }
                    if (a[iv][jv] != 0)
                        continue;
                    if (iv >= 1 && iv <= n && jv >= 1 && jv <= m && 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;
}