Cod sursa(job #2140138)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 23 februarie 2018 01:26:29
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <iostream>
#include <fstream>
#include <climits>
#include <deque>
#define dimm 505
#define dirs 8
#define mval INT_MAX

std::ifstream f("car.in");
std::ofstream g("car.out");

int N, M, zid[dimm][dimm];
int y0, x0, y1, x1;

int cost[dimm][dimm][dirs];
int grad[] = {7, 1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1}, dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
int totul_are_un_cost() {
    for (int i=1, j, k; i<=N; i++)
        for (j=1; j<=M; j++)
            for (k=0; k<dirs; k++)
                cost[i][j][k] = mval;

    struct nod {int y, x, dir;};
    std::deque <nod> dq;
    for (int i=0; i<dirs; i++) {
        cost [y0][x0][i] = 0;
        dq.push_back({y0, x0, i});
    }

    nod pres, nou;
    while(!dq.empty()) {
        pres = dq.front();
        dq.pop_front();

        if(pres.y == y1 && pres.x == x1)
            return cost[y1][x1][pres.dir];

        //varianta preferabila: ne continuam directia
        nou = pres; nou.y += dy[pres.dir]; nou.x += dx[pres.dir];
        if(!zid[nou.y][nou.x] && cost[nou.y][nou.x][nou.dir] > cost[pres.y][pres.x][pres.dir])
            dq.push_front(nou), cost[nou.y][nou.x][nou.dir] = cost[pres.y][pres.x][pres.dir];

        //treceri intre directii
        for (int i=0; i<2; i++) {
            int v = grad[i];
            nou = pres; int d = (pres.dir + v)%dirs;
            nou.dir = d;
            if(!zid[nou.y][nou.x] && cost[nou.y][nou.x][nou.dir] > cost[pres.y][pres.x][pres.dir] + 1)
                dq.push_back(nou), cost[nou.y][nou.x][nou.dir] = cost[pres.y][pres.x][pres.dir] + 1;
        }
    } return -1;
}

void citire() {
    f >> N >> M;
    f >> y0 >> x0 >> y1 >> x1;
    for (int i=0, j; i<N; i++)
        for (j=0; j<M; j++)
            f >> zid[i+1][j+1];
}
void rezolvare() {
    g << totul_are_un_cost();
}

int main()
{
    citire();
    rezolvare();

    return 0;
}