Cod sursa(job #3327281)

Utilizator Mihai_OctMihai Octavian Mihai_Oct Data 2 decembrie 2025 23:38:47
Problema Car Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("car.in");
ofstream fout("car.out");
const int DI[] = {-1, -1, 0, 1, 1,  1,  0, -1};
const int DJ[] = { 0,  1, 1, 1, 0, -1, -1, -1};
int n, m, i, j, incI, incJ, sfI, sfJ;
int cost[502][502][8], rasp;
bool bloc[502][502];

static inline void Lee() {
    queue<tuple<int, int, int>> q;
    for(i = 0; i < 8; i++) {
        cost[incI][incJ][i] = 0;
        q.push(make_tuple(incI, incJ, i));
    }

    while(!q.empty()) {
        int i, j, d;
        tie(i, j, d) = q.front();
        q.pop();

        for(int dir = -3; dir < 4; dir++) {
            int costAdd = (dir < 0 ? -dir : dir);
            int dirCur = (dir + d + 8) % 8;

            int in = i + DI[dirCur];
            int jn = j + DJ[dirCur];

            if(!bloc[in][jn] && (1 <= in && in <= n && 1 <= jn && jn <= m)) {
                if(cost[in][jn][dirCur] == -1 || cost[in][jn][dirCur] > cost[i][j][d] + costAdd)
                cost[in][jn][dirCur] = cost[i][j][d] + costAdd;
                q.push({in, jn, dirCur});
            }
        }
    }
}

int main() {
    fin.tie(nullptr);
    fout.tie(nullptr);

    fin >> n >> m;
    fin >> incI >> incJ;
    fin >>  sfI >>  sfJ;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            fin >> bloc[i][j];

            for(int k = 0; k < 8; k++) {
                cost[i][j][k] = -1;
            }
        }
    }

    Lee();

    rasp = INT_MAX;
    for(i = 0; i < 8; i++) {
        if(cost[sfI][sfJ][i] != -1) rasp = min(rasp, cost[sfI][sfJ][i]);
    }
    fout << rasp;

    return 0;
}