Cod sursa(job #1703268)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 16 mai 2016 18:00:20
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 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{
    int x;
    int y;
    int dirr;
};
deque<elem> c[750005];
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};
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;
    for(i = 0; i <= lg; i++){
        while(!c[i].empty()){
            ii = c[i].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;
                        c[i + cost(dir, ii.dirr)].push_back(aux);
                    }
                }
            }
            c[i].pop_front();
        }
    }
    sol = INF;
    for(i = 0; i < 8; i++){
        sol = min(sol, d[ii2][jj2][i]);
    }
    fout<< sol <<"\n";
    return 0;
}