Cod sursa(job #1703288)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 16 mai 2016 18:28:55
Problema Car Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
#include<fstream>
#include<deque>
#define INF 1000000000
using namespace std;
int n, m, i, j, ii1, jj1, ii2, jj2, dir, k, iv, jv, lg, sol;
int a[505][505], d[505][505][8];
struct elem{
    short x;
    short y;
    char dirr;
};
deque<elem> c[6];
elem aux, ii;
int di[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dj[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int mod(int x){
    if(x >= 5){
        return x - 5;
    }
    return x;
}
ifstream fin("car.in");
ofstream fout("car.out");
int cost(int a, int b){
    if(a > b){
        swap(a, b);
    }
    int x = min(b - a, a + 8 - b);
    return x;
}
int main(){
    fin>> n >> m >> ii1 >> jj1 >> ii2 >> jj2;
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            fin>> a[i][j];
            for(dir = 0; dir < 8; dir++){
                d[i][j][dir] = INF;
            }
        }
    }
    for(dir = 0; dir < 8; dir++){
        aux.x = ii1;
        aux.y = jj1;
        aux.dirr = dir;
        c[0].push_back(aux);
    }
    lg = n * m * 3;
    k = 0;
    for(i = 0; i <= lg; i++){
        while(!c[k].empty()){
            ii = c[k].front();
            if(d[ii.x][ii.y][ii.dirr] == INF){
                d[ii.x][ii.y][ii.dirr] = i;
                for(dir = 0; dir < 8; dir++){
                    iv = ii.x + di[dir];
                    jv = ii.y + dj[dir];
                    if(iv >= 1 && iv <= n && jv >= 1 && jv <= m && a[iv][jv] == 0 && d[iv][jv][dir] == INF){
                        aux.x = iv;
                        aux.y = jv;
                        aux.dirr = dir;
                        if(cost(dir, ii.dirr) <= 4){
                            c[  mod(i + cost(dir, ii.dirr) ) ].push_back(aux);
                        }
                    }
                }
            }
            c[k].pop_front();
        }
        k++;
        k = mod(k);
    }
    sol = INF;
    for(i = 0; i < 8; i++){
        sol = min(sol, d[ii2][jj2][i]);
    }
    if(sol == INF){
        fout<<"-1\n";
        return 0;
    }
    fout<< sol <<"\n";
    return 0;
}