Cod sursa(job #2847758)

Utilizator vladth11Vlad Haivas vladth11 Data 11 februarie 2022 13:47:16
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.59 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;

struct ura {
    int i, j, d;
};

int dp[501][501][8];
bitset <501> mat[501];
bool viz[501][501][8];
short dx[] = {0, 1, 1, 1, 0, -1, -1, -1};
short dy[] = {1, 1, 0, -1, -1, -1, 0, 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 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++) {
            int a;
            cin >> a;
            if(a == 1)
                mat[i].flip(j);
        }
    }
    if(mat[si][sj] == 1) {
        cout << -1;
        return 0;
    }
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            for(int d = 0; d < 8; d++) {
                dp[i][j][d] = 1e9;
            }
        }
    }
    deque <ura> v;

    for(int i = 0; i < 8; i++) {
        dp[si][sj][i] = 0;
        v.push_back({si, sj, i});
    }
    while(v.size()) {
        ura x = v.front();
        v.pop_front();
        if(viz[x.i][x.j][x.d])
            continue;
        viz[x.i][x.j][x.d] = true;
        int i = x.i;
        int j = x.j;
        int d = x.d;
        int ni = i + dx[d];
        int nj = j + dy[d];
        if(OK(ni, nj)) {
            if(dp[ni][nj][d] > dp[i][j][d]) {
                dp[ni][nj][d] = dp[i][j][d];
                v.push_front({ni, nj, d});
            }
        }
        int d1 = d + 1;
        if(d1 == 8)
            d1 = 0;
        if(dp[i][j][d1] > dp[i][j][d] + 1) {
            dp[i][j][d1] = dp[i][j][d] + 1;
            v.push_back({i, j, d1});
        }
        d1 = d - 1;
        if(d1 == -1)
            d1 = 7;
        if(dp[i][j][d1] > dp[i][j][d] + 1) {
            dp[i][j][d1] = dp[i][j][d] + 1;
            v.push_back({i, j, d1});
        }
    }
    int minim = 1e9;
    for(int i = 0; i < 8; i++) {
        minim = min(minim, dp[fi][fj][i]);
    }
    if(minim == 1e9) {
        cout << -1;
        return 0;
    }
    cout << minim;
    return 0;
}