Cod sursa(job #2710503)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 22 februarie 2021 17:16:46
Problema Car Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <bits/stdc++.h>

using namespace std;

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

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

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

void solve() {
    for(int k = 0; k < 8; ++k) {
        int val = (istart << 12) + (jstart << 3) + k;
        l[0][++sz[0]] = val;
        viz[val] = best[val] = 1;
    }
    int ind = 0;
    while(sz[ind]) {
        int nxt = ind ^ 1;
        for(int k = 1; k <= sz[ind]; ++k)
            if(viz[l[ind][k]] == 1) {
                int val = l[ind][k];
                int dir = val & 7,
                    j = (val & (511 << 3)) >> 3,
                    i = (val & (511 << 12)) >> 12;
                int cost = 0;
                for(const int &add : {0, 1, -2}) {
                    dir = (dir + add + 8) % 8;
                    int iv, jv;
                    if(add == 0)
                        iv = i + di[dir], jv = j + dj[dir];
                    else
                        iv = i, jv = j;
                    int new_val = (iv << 12) + (jv << 3) + dir;
                    if(inside(iv, jv) && !a[iv][jv] && (!viz[new_val] || (add == 0 && best[new_val] > best[val]))) {
                        viz[new_val] = 1;
                        best[new_val] = best[val] + cost;
                        l[nxt][++sz[nxt]] = new_val;
                    }
                    if(add == 0)
                        cost = 1;
                }
                if(i == istop && j == jstop) {
                    ans = best[val];
                    return;
                }
                viz[val] = 2;
            }
        sz[ind] = 0;
        ind = nxt;
    }
}

int main() {
    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];
    solve();
    fout << ans - 1 << '\n';
}