Cod sursa(job #3366288)

Utilizator flipiiiTatucu Filip flipiii Data 30 septembrie 2026 13:00:24
Problema Car Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <bits/stdc++.h>
using namespace std;
int mat[1001][1001], dist[1001][1001][8], n, m;
int di[]={-1, -1, -1, 0, 1, 1, 1, 0}, dj[]={-1, 0, 1, 1, 1, 0, -1, -1};
queue<int> lst;

bool check(int x, int y) {
    if (x>0 && x<=n && y>0 && y<=m && mat[x][y]==0) return true;
    return false;
}
void lee(int a1, int a2) {
    queue<pair<int, int>> q;
    for (int i=0; i<8; i++) {
        dist[a1][a2][i]=0;
        q.push(make_pair(a1, a2));
        lst.push(i);
    }
    while(!q.empty()) {
        int i = q.front().first, j = q.front().second, l=lst.front();
        q.pop();
        lst.pop();
        for(int k = 0; k < 8; k++) {
            int x = i + di[k], y = j + dj[k];
            int p;
            p=min(max(k,l)-min(k, l), 8-max(k, l)+min(k, l));
            //int p=k;
            // if (max(k, l) - min(k, l) > 4) {
            //     if (k>l)
            //         l+=8;
            //     else
            //         p=k+8;
            // }
            //p=l-p;
            //if (p<0)
            //   p=-p;
            if (check(x, y) && dist[x][y][k] > dist[i][j][l] + p) {
                dist[x][y][k] = dist[i][j][l]+p;
                q.push(make_pair(x, y));
                lst.push(k);
            }
        }
    }
}
int main() {
    ifstream cin("car.in");
    ofstream cout("car.out");
    cin >> n >> m;
    int pl, pc, cl, cc;
    cin >> pl >> pc >> cl >> cc;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mat[i][j];
            for (int k = 0; k < 8; k++) {
                dist[i][j][k]=1e9;
            }
        }
    }
    lee(pl, pc);
    int ans=1e9;
    for (int i=0; i<8; i++) {
        ans=min(ans, dist[cl][cc][i]);
    }
    if (ans==1e9)
        ans=-1;
    cout << ans << endl;
    return 0;
}