Cod sursa(job #1500588)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 12 octombrie 2015 10:52:33
Problema Car Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("car.in");
ofstream fout("car.out");

const int NMax = 505;
const int INF = 1e9;
const int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};

bool v[NMax][NMax];
int val[NMax][NMax];

deque < int > Dir, Qx, Qy;

inline void Solve(const int &x, const int &y, const int &a, const int &value){
    int nx, ny;
    nx = x + dx[a];
    ny = y + dy[a];
    if(!v[nx][ny] && val[x][y] + value < val[nx][ny]){
        val[nx][ny] = val[x][y] + value;
        Qx.push_back(nx);
        Qy.push_back(ny);
        Dir.push_back(a);
    }
}

inline void Lee(){
    int x, y, D, lo, hi;
    while(!Qx.empty()){
        x = Qx.front(); Qx.pop_front();
        y = Qy.front(); Qy.pop_front();
        D = Dir.front(); Dir.pop_front();
        lo = hi = D;
        for(int i = 0; i < 5; i++){
            Solve(x, y, lo, i);
            if(lo != hi){
                Solve(x, y, hi, i);
            }
            lo--;
            if(lo < 0) lo = 7;
            hi++;
            if(hi > 7) hi = 0;
        }
    }
}

int main(){
    int n, m, x, y, X, Y;
    fin >> n >> m >> x >> y >> X >> Y;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            fin >> v[i][j];
        }
    }
    for(int i = 0; i <= n + 1; i++){
        v[i][0] = v[i][m + 1] = 1;
    }
    for(int i = 0; i <= m + 1; i++){
        v[0][i] = v[n + 1][i] = 1;
    }
    for(int i = 0; i < 8; i++){
        Qx.push_back(x);
        Qy.push_back(y);
        Dir.push_back(i);
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            val[i][j] = INF;
        }
    }
    val[x][y] = 0;
    Lee();
    fout << val[X][Y];
    return 0;
}