Cod sursa(job #2139918)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 22 februarie 2018 21:32:23
Problema Car Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <iostream>
#include <fstream>
#include <queue>
#define dimm 505
#define mval 1000005

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

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

int curba(int d1, int d2) {
    int v;
    if(d1==d2+4) v=4;
    else if(d2==d1+4) v=4;
    else v = std::max((d1-d2)%4, (d2-d1)%4);
    return v;
}

int cost[dimm][dimm];
struct nod {int y, x, dir;};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1}, dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
void totul_are_un_cost() {
    std::queue <nod> q;
    q.push({y0, x0, 0});

    for (int i=1, j; i<=N; i++)
        for (j=1; j<=M; j++)
            cost[i][j] = mval;

    nod pres, nou;
    cost[y0][x0] = 0;

    pres = q.front();
    for (int i=0; i<8; i++) {
        nou = pres; nou.dir = i;
        nou.y += dy[i]; nou.x += dx[i];

        int c = 0;
        if(!zid[nou.y][nou.x] && (cost[nou.y][nou.x] > cost[pres.y][pres.x] + c)) {
            cost[nou.y][nou.x] = cost[pres.y][pres.x] + c;
            q.push(nou);
        }
    }

    while(!q.empty()) {
        pres = q.front();
        q.pop();

        for (int i=0; i<8; i++) {
            nou = pres; nou.dir = i;
            nou.y += dy[i]; nou.x += dx[i];

            int c = curba(nou.dir, pres.dir);
            if(!zid[nou.y][nou.x] && (cost[nou.y][nou.x] > cost[pres.y][pres.x] + c)) {
                cost[nou.y][nou.x] = cost[pres.y][pres.x] + c;
                q.push(nou);
            }
        }
    }
}

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() {
    totul_are_un_cost();
    if(cost[y1][x1] == mval) cost[y1][x1] = -1;
    g << cost[y1][x1];
}

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

    return 0;
}