Cod sursa(job #2847744)

Utilizator vladth11Vlad Haivas vladth11 Data 11 februarie 2022 13:05:21
Problema Car Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.69 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];

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

bool mat[501][501];
int dx[] = {0, 1, 0, -1, 1, -1, -1, 1};
int dy[] = {1, 0, -1, 0, 1, 1, -1, -1};
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 ind(int a, int b, int c) {
    return (a - 1) * m * 8 + (b - 1) * 8 + (c + 1);
}

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++) {
                dp[ind(i, j, d)] = 1e9;
            }
        }
    }
    int goodL = ind(fi, fj, 0);
    int goodR = ind(fi, fj, 7);
    for(int i = 0; i < 8; i++) {
        dp[ind(si, sj, i)] = 0;
        v[0].push_back(ind(si, sj, i));
    }
    int act = 0;
    while(act < NMAX) {
        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;
            viz[x] = 1;
            int d = x % 8 - 1;
            if(d == -1)
                d = 7;
            j = (x / 8) % m;
            j++;
            i = (x / 8 / m) + 1;
            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]);
                pii y = {nou, cost};
                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;
}