Cod sursa(job #2710574)

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

using namespace std;

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

const short NMAX = 512;
short N, M, istart, jstart, istop, jstop;
bool a[NMAX][NMAX];
short viz[1 << 22], best[1 << 22], ans;
const int di[8] = {-1, -1, 0, 1, 1, 1, 0, -1},
          dj[8]	= {0, 1, 1, 1, 0, -1, -1, -1};

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() {
    deque<int> Q;
    for(int k = 0; k < 8; ++k) {
        int val = (istart << 12) + (jstart << 3) + k;
        Q.push_back(val);
        viz[val] = best[val] = 1;
    }
    while(!Q.empty()) {
        int val = Q.front();
        Q.pop_front();
        if(viz[val] != 1)
            continue;
        int dir = val & 7,
            j = (val & (511 << 3)) >> 3,
            i = (val & (511 << 12)) >> 12;
        int iv = i + di[dir],
            jv = j + dj[dir];
        if(inside(iv, jv) && !a[iv][jv]) {
            int nxt_val = (iv << 12) + (jv << 3) + dir;
            if(!viz[nxt_val] || best[nxt_val] > best[val]) {
                viz[nxt_val] = 1;
                best[nxt_val] = best[val];
                Q.push_front(nxt_val);
            }
        }
        if(!a[i][j]) {
            dir = (dir + 1) % 8;
            int nxt_val = (i << 12) + (j << 3) + dir;
            if(!viz[nxt_val]) {
                viz[nxt_val] = 1;
                best[nxt_val] = best[val] + 1;
                Q.push_back(nxt_val);
            }
            nxt_val -= dir;
            dir = (dir + 6) % 8;
            nxt_val += dir;
            if(!viz[nxt_val]) {
                viz[nxt_val] = 1;
                best[nxt_val] = best[val] + 1;
                Q.push_back(nxt_val);
            }
        }
        if(i == istop && j == jstop) {
            ans = best[val];
            return;
        }
        viz[val] = 2;
    }
}

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