Cod sursa(job #3327307)

Utilizator Mihai_OctMihai Octavian Mihai_Oct Data 3 decembrie 2025 10:54:52
Problema Car Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.11 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 long long Encode(int i, int j, int d) {
    return d + j * 10 + i * 10000;
}

static inline void Lee() {
    queue<long long> q[3];
    for(int dir = 0; dir < 8; dir++) {
        cost[incI][incJ][dir] = 0;
        q[0].push(Encode(incI, incJ, dir));
    }

    int coada = 0;
    while(!q[0].empty() || !q[1].empty() || !q[2].empty()) {
        while(q[coada].empty()) coada = (coada + 1) % 3;

        int i = q[coada].front() / 10000 % 1000;
        int j = q[coada].front() / 10    % 1000;
        int d = q[coada].front()         % 10;
        q[coada].pop();
        //cout << "! " << i << " " << j << " : " << d << "\n";

        for(int rot = -2; rot <= 2; rot++) {
            int costAdd = (rot < 0 ? -rot : rot);
            int dir = (d + rot + 8) % 8;

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

            if(!bloc[in][jn] && (1 <= in && in <= n && 1 <= jn && jn <= m)) {
                if(cost[in][jn][dir] > cost[i][j][d] + costAdd) {
                    cost[in][jn][dir] = cost[i][j][d] + costAdd;
                    q[cost[in][jn][dir] % 3].push(Encode(in, jn, dir));
                    //cout << "+ " << cost[in][jn][dir] % 3 << " -> " << in << " " << jn << " : " << dir << "\n";
                }
            }
        }
    }
}

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] = 1e9;
            }
        }
    }

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