Cod sursa(job #899991)

Utilizator NikitaUtiuNichita Utiu NikitaUtiu Data 28 februarie 2013 17:14:57
Problema Car Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <fstream>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

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

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]; 
}

queue <stare> coada[2];

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[0].push(stare(k, xs, ys));
    }
    
    int nx, ny, ndir, curent = 0;
    while(!(coada[0].empty() && coada[1].empty())) {
        stare varf = coada[curent].front();
        coada[curent].pop();
        
        if(varf.x == xe && varf.y == ye)
            break;
        
        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[0].push(stare(ndir, nx, ny));
        }
        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[1].push(stare(ndir, nx, ny));
        }
        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[1].push(stare(ndir, nx, ny));
        }
        curent = (coada[curent].empty() ? 1 - curent : curent);
    }
    
    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();
}