Cod sursa(job #1893231)

Utilizator marcdariaDaria Marc marcdaria Data 25 februarie 2017 15:58:18
Problema Car Scor 100
Compilator cpp Status done
Runda becreative23 Marime 2.25 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, ab, jj;
int a[505][505], d[505][505][8], ad[8][8], ll[8];

struct elem{
    short x;
    short y;
    char dirr;
};

deque<elem> c[5];
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 mod(int x){
    if(x < 3){
        return x;
    }
    else{
        return x - 3;
    }
}
void add(int iv, int jv, int dir, int val){
      if(iv >= 1 && iv <= n && jv >= 1 && jv <= m && a[iv][jv] == 0 && d[iv][jv][dir] >  val){
            d[iv][jv][dir] = val;
            aux.x = iv;
            aux.y = jv;
            aux.dirr = dir;
            c[ (d[iv][jv][dir] & 1) ].push_back(aux);
        }
}
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++){
        d[ii1][jj1][dir] = 0;
        aux.x = ii1;
        aux.y = jj1;
        aux.dirr = dir;
        c[0].push_back(aux);
    }
    for(i = 0; i < 8; i++){
        for(j = 0; j < 8; j++){
            if(cost(i, j) == 1){
                ad[i][++ll[i] ] = j;
            }
        }
    }
    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] == i){
                add(ii.x + di[ii.dirr], ii.y + dj[ii.dirr], ii.dirr, d[ii.x][ii.y][ii.dirr]);
                for(jj = 1; jj <= 2; jj++){
                    add(ii.x, ii.y, ad[ii.dirr][jj], d[ii.x][ii.y][ii.dirr] + 1);
                }
            }
            c[k].pop_front();
        }
        k = 1 - 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;
}