Cod sursa(job #2646989)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 2 septembrie 2020 17:03:50
Problema Car Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 505

int n,m,sx,sy,fx,fy,mn[NMAX][NMAX][8],cst[8][8];
bool mat[NMAX][NMAX];

int dx[] = {-1,-1,0,1,1,1,0,-1};
int dy[] = {0,1,1,1,0,-1,-1,-1};

struct ceva{
    int x,y,d,cst;
};

vector<ceva> Q[3];

bool comp(ceva A, ceva B){
    return A.cst > B.cst;
}

bool OK(int x, int y){
    if (x <= 0 || x > n || y <= 0 || y > m) return 0;
    return 1;
}

int main()
{
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);

    cin >> n >> m;
    cin >> sx >> sy >> fx >> fy;

    for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++){
        cin >> mat[i][j];
    }

    for (int i=0;i<8;i++){
        for (int j=0;j<8;j++){
            cst[i][j] = min(abs(j-i), 8 - max(i,j) + min(i,j));
        }
    }

    memset(mn,0x3f,sizeof(mn));
    for (int i=0;i<8;i++){
        mn[sx][sy][i] = 0;
        Q[0].push_back({sx, sy, i, 0});
    }

    int t = 0;
    while (!(Q[0].empty() && Q[1].empty() && Q[2].empty())){
        for (int i=0;i<Q[t].size();i++){
            ceva crt = Q[t][i];

            if (crt.cst > mn[crt.x][crt.y][crt.d]) continue;
//            cerr << crt.x << ' ' << crt.y << ' ' << crt.d << ' ' << crt.cst << '\n';

            for (int k=0;k<8;k++){
                int x = crt.x + dx[k];
                int y = crt.y + dy[k];
                if (!OK(x,y)) continue;
                if (mat[x][y] == 1) continue;
                int d = k;
                if (cst[crt.d][k] > 2) continue;
                int newCst = cst[crt.d][k] + crt.cst;

                if (newCst < mn[x][y][d]){
                    mn[x][y][d] = newCst;
                    Q[(t + newCst) % 3].push_back({x,y,d,newCst});
                }
            }
        }
        Q[t].clear();
        t++;
        t %= 3;
    }

    int ans = 1e9;
    for (int i=0;i<8;i++) ans = min(ans, mn[fx][fy][i]);

    if (ans > 1e8) cout << "-1\n";
    else cout << ans << '\n';


    return 0;
}