Cod sursa(job #2710584)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 22 februarie 2021 19:09:47
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("car.in");
ofstream fout("car.out");

class node {
    public:
        int i, j, dir;
};

const short NMAX = 512;
const short di[8] = {-1, -1, 0, 1, 1, 1, 0, -1},
            dj[8] = {0, 1, 1, 1, 0, -1, -1, -1};
short N, M, istart, jstart, istop, jstop;
bool a[NMAX][NMAX];
short viz[NMAX][NMAX][8], dp[NMAX][NMAX][8], ans;
deque<node> Q;

bool inside(const int &lin, const int &col) {
    return lin > 0 && col > 0 && lin <= N && col <= M;
}

void read() {
    fin >> N >> M >> istart >> jstart >> istop >> jstop;
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
            fin >> a[i][j];
}

void solve() {
    for(int k = 0; k < 8; ++k) {
        Q.push_back(node{istart, jstart, k});
        viz[istart][jstart][k] = dp[istart][jstart][k] = 1;
    }
    while(!Q.empty()) {
        int i = Q.front().i,
            j = Q.front().j,
            dir = Q.front().dir;
        Q.pop_front();
        if(viz[i][j][dir] != 1)
            continue;
        int iv = i + di[dir],
            jv = j + dj[dir];
        if(inside(iv, jv) && !a[iv][jv])
            if(!viz[iv][jv][dir] || dp[iv][jv][dir] > dp[i][j][dir]) {
                viz[iv][jv][dir] = 1;
                dp[iv][jv][dir] = dp[i][j][dir];
                Q.push_front(node{iv, jv, dir});
            }
        int aux = dir;
        if(!a[i][j])
            for(const int &add : {1, 6}) {
                dir = (dir + add) % 8;
                if(!viz[i][j][dir]) {
                    viz[i][j][dir] = 1;
                    dp[i][j][dir] = dp[i][j][aux] + 1;
                    Q.push_back(node{i, j, dir});
                }
            }
        if(i == istop && j == jstop) {
            ans = dp[i][j][aux];
            return;
        }
        viz[i][j][aux] = 2;
    }
}

int main() {
    read();
    solve();
    fout << ans - 1 << '\n';
}