Cod sursa(job #899863)

Utilizator NikitaUtiuNichita Utiu NikitaUtiu Data 28 februarie 2013 16:41:32
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <fstream>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

struct stare {
    int dir, x, y;
    bool ch;
    stare (int _dir, int _x, int _y, bool _ch) : dir(_dir) ,x(_x), y(_y), ch(_ch) {}
};

int n, m, xs, ys, xe, ye;
bool a[500][500];
int minim[8][500][500];

const int INF = 0x3f3f3f3f;
const int dx[8] = {0, -1, -1, -1, 0, 1, 1, 1},
          dy[8] = {1, 1, 0, -1, -1, -1, 0, 1};

inline bool ok(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m && !a[x][y]; 
}

struct comp {
    bool operator()(stare a, stare b) {
        if(a.ch != b.ch)
            return a.ch && !b.ch;
        return minim[a.dir][a.x][a.y] > minim[b.dir][b.x][b.y];
    }
};

priority_queue <stare, vector <stare>, comp> coada;

int main(void) {
    ifstream fin("car.in");
    fin >> n >> m;
    fin >> xs >> ys >> xe >> ye;
    --xs, --ys, --xe, --ye;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            fin >> a[i][j];
    fin.close();
    
    for(int k = 0; k < 8; ++k)
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                minim[k][i][j] = INF;
    
    for(int k = 0; k < 8; ++k) {
        minim[k][xs][ys] = 0;
        coada.push(stare(k, xs, ys, false));
    }
    
    int nx, ny, ndir;
    while(!coada.empty()) {
        stare varf = coada.top();
        //stare varf = coada.front();
        coada.pop();
        
        ndir = varf.dir; nx = varf.x + dx[ndir], ny = varf.y + dy[ndir];
        if(ok(nx, ny) && minim[ndir][nx][ny] > minim[varf.dir][varf.x][varf.y]) {
            minim[ndir][nx][ny] = minim[varf.dir][varf.x][varf.y];
            coada.push(stare(ndir, nx, ny, false));
        }
        ndir = (varf.dir + 9) % 8; nx = varf.x, ny = varf.y;
        if(minim[ndir][nx][ny] > minim[varf.dir][varf.x][varf.y] + 1) {
            minim[ndir][nx][ny] = minim[varf.dir][varf.x][varf.y] + 1;
            coada.push(stare(ndir, nx, ny, true));
        }
        ndir = (varf.dir + 7) % 8; nx = varf.x, ny = varf.y;
        if(minim[ndir][nx][ny] > minim[varf.dir][varf.x][varf.y] + 1) {
            minim[ndir][nx][ny] = minim[varf.dir][varf.x][varf.y] + 1;
            coada.push(stare(ndir, nx, ny, true));
        }
    }
    
    int best = INF;
    for(int k = 0; k < 8; ++k)
        best = min(best, minim[k][xe][ye]);
    
    ofstream fout("car.out");
    fout << (best == INF ? -1 : best);
    fout.close();
}