Cod sursa(job #2764567)

Utilizator DragosC1Dragos DragosC1 Data 21 iulie 2021 17:00:31
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <fstream>
#include <deque>
#include <iostream>
using namespace std;

int istart, jstart, istop, jstop;
int n, m;
int a[501][501];

void read() {
    int i, j;
    ifstream f("car.in");
    f >> n >> m;
    f >> istart >> jstart >> istop >> jstop;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            f >> a[i][j];
    f.close();
}

struct tripla {
    int x, y, dir;
};

deque<tripla> dq;

const int di[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dj[] = {0, 1, 1, 1, 0, -1, -1, -1};

int viz[505][505][8];
int cost[505][505][8];

const int Inf = 1e9;
int rez = -1;

bool inside(int i, int j) {
    if (i >= 1 && j >= 1 && i <= n && j <= m)
        return 1;
    return 0;
}

void solve() {
    int k, i, j, inou, jnou, dir;

    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            for (k = 0; k < 8; k++)
                cost[i][j][k] = Inf;

    for (k = 0; k < 8; k++) {
        viz[istart][jstart][k] = 1;
        cost[istart][jstart][k] = 0;
        dq.push_back({istart, jstart, k});
    }

    while (!dq.empty()) {
        int i = dq.front().x, j = dq.front().y, dir = dq.front().dir;
        dq.pop_front();
        if (viz[i][j][dir] != 1) 
            continue;
        inou = i + di[dir], jnou = j + dj[dir];
        if (inside(inou, jnou) && !a[inou][jnou] && (!viz[inou][jnou][dir] || cost[inou][jnou][dir] > cost[i][j][dir])) {
            viz[inou][jnou][dir] = 1;
            cost[inou][jnou][dir] = cost[i][j][dir];
            dq.push_front({inou, jnou, dir});
        }
        if (!a[i][j]) 
            for (int k : {dir + 1, dir + 7}) 
                if (!viz[i][j][k % 8]) {
                    viz[i][j][k % 8] = 1;
                    cost[i][j][k % 8] = cost[i][j][dir] + 1;
                    dq.push_back({i, j, k % 8});
                }
        if (i == istop && j == jstop) {
            rez = cost[i][j][dir];
            return;
        }
        viz[i][j][dir] = 2;
    }
}

void output() {
    ofstream g("car.out");
    g << rez;
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}