Mai intai trebuie sa te autentifici.

Cod sursa(job #3360297)

Utilizator Andrei_GAndreiG Andrei_G Data 11 iulie 2026 16:43:02
Problema Car Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <iostream>
#pragma GCC optimize("O3,unroll-loops")
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iomanip>
#include <numeric>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#define int long long
//#define int short
using namespace std;

const int nmax = 500;
const int dirmax = 8;
const int inf = 1e9;

int n, m, v[nmax + 5][nmax + 5], d[nmax + 5][nmax + 5][dirmax], istart, jstart, iend, jend;
int dx[] = {0, -1, -1, -1, 0, 1, 1, 1};
int dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};

struct Car{
    int i;
    int j;
    int dir;
    int dis;
};

bool inm(int i, int j){
    if (i >= 1 && i <= n && j >= 1 && j <= m){
        return true;
    }
    return false;
}

void dijkstra(){
    deque<Car> dq[5];
    for (int dir = 0; dir < 8; dir++){
        d[istart][jstart][dir] = 0;
        dq[0].push_back({istart, jstart, dir, 0});
    }
    while (!dq[0].empty() || !dq[1].empty() || !dq[2].empty() || !dq[3].empty()){
        while (dq[0].empty()){
            dq[0] = dq[1];
            dq[1] = dq[2];
            dq[2] = dq[3];
            dq[3] = dq[4];
            dq[4].clear();
        }
        Car currcar = dq[0].front(); dq[0].pop_front();
        if (currcar.dis > d[currcar.i][currcar.j][currcar.dir]){
            continue;
        }
        for (int dir = 0; dir < 8; dir++){
            int ni = currcar.i + dx[dir];
            int nj = currcar.j + dy[dir];
            int ndis = currcar.dis + ((abs(currcar.dir - dir) > 4) ? 8 - abs(currcar.dir - dir) : abs(currcar.dir - dir));
            if (inm(ni, nj) && !v[ni][nj] && ndis < d[ni][nj][dir]){
                d[ni][nj][dir] = ndis;
                dq[ndis - currcar.dis].push_back({ni, nj, dir, ndis});
            }
        }
    }
}

int GetSmallestDis(int i, int j){
    int mn = inf;
    for (int dir = 0; dir < 8; dir++){
        mn = min(mn, d[i][j][dir]);
    }
    return mn;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("car.in", "r", stdin);
    freopen("car.out", "w", stdout);
    cin>>n>>m>>istart>>jstart>>iend>>jend;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin>>v[i][j];
            for (int dir = 0; dir < 8; dir++){
                d[i][j][dir] = inf;
            }
        }
    }
    dijkstra();
    cout<<GetSmallestDis(iend, jend);
}