Cod sursa(job #2847736)

Utilizator vladth11Vlad Haivas vladth11 Data 11 februarie 2022 12:44:32
Problema Car Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.87 kb
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 501 * 501 * 8;
const ll VMAX = 21;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 447;
const ll base = 31;
const ll nr_of_bits = 21;

vector <int> v[NMAX];
vector <pii> g[NMAX];

int dp[NMAX];
int viz[NMAX];

int mat[501][501];
int dx[] = {0, 1, 0, -1, 1, -1, -1, 1};
int dy[] = {1, 0, -1, 0, 1, 1, -1, -1};
int ind[501][501][8];
int n, m;

bool OK(int i, int j){
    if(i < 1 || i > n || j < 1 || j > m)
        return false;
    return (mat[i][j] == 0);
}

int main() {
    ifstream cin("car.in");
    ofstream cout("car.out");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int i, j, si, sj, fi, fj;
    cin >> n >> m >> si >> sj >> fi >> fj;
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++)
            cin >> mat[i][j];
    }
    if(mat[si][sj] == 1){
        cout << -1;
        return 0;
    }
    int cnt = 0;
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            for(int d = 0; d < 8; d++){
                ind[i][j][d] = ++cnt;
                dp[cnt] = 1e9;
            }
        }
    }
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            if(mat[i][j] == 1)
                continue;
            for(int d = 0; d < 8; d++){
                int nod = ind[i][j][d];
                for(int d1 = 0; d1 < 8; d1++){
                    int ni = i + dx[d1];
                    int nj = j + dy[d1];
                    if(!OK(ni, nj))
                        continue;
                    int nou = ind[ni][nj][d1];
                    int cost = max(dx[d], dx[d1]) - min(dx[d], dx[d1]) + max(dy[d], dy[d1]) - min(dy[d], dy[d1]);
                    g[nod].push_back({nou, cost});
                }
            }
        }
    }
    int goodL = ind[fi][fj][0];
    int goodR = ind[fi][fj][7];
    for(int i = 0; i < 7; i++){
        dp[ind[si][sj][i]] = 0;
        v[0].push_back(ind[si][sj][i]);
    }
    int act = 0;
    while(act < NMAX){
        //debug(act);
        while(v[act].size()){
            int x = v[act].back();
            v[act].pop_back();
            if(goodL <= x && x <= goodR){
                cout << act << "\n";
                return 0;
            }
            if(viz[x])
                continue;
            //debug(x);
            viz[x] = 1;
            for(auto y : g[x]){
                if(dp[y.first] > y.second + dp[x]){
                    dp[y.first] = y.second + dp[x];
                    v[dp[y.first]].push_back(y.first);
                }
            }
        }
        act++;
    }
    cout << -1;
    return 0;
}