Cod sursa(job #2646994)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 2 septembrie 2020 17:19:26
Problema Car Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.51 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;
};

ceva Q[3][260000];

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

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

//    cout << "500 500\n1 1 500 500\n";
//    for (int i=1;i<=500;i++,cout << '\n')
//        for (int j=1;j<=500;j++)
//            if (j%2==0){
//                if (j%4==2 && i==500 || j%4==0 && i==1) cout << 0 << ' ';
//                else cout << 1 << ' ';
//            }
//            else
//                cout << 0 << ' ';
//
//    return 0;

    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<=n+1;i++) mat[i][0] = mat[i][m+1] = 1;
    for (int j=0;j<=m+1;j++) mat[0][j] = mat[n+1][j] = 1;

    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][++Q[0][0].d] = {sx, sy, i, 0};
    }

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

            if (crt.cst > mn[crt.x][crt.y][crt.d]) continue;
//            if (crt.x == fx && crt.y == fy){
//                cout << crt.cst << '\n';
//                return 0;
//            }
//            cerr << crt.x << ' ' << crt.y << ' ' << crt.d << ' ' << crt.cst << '\n';

            for (int k=(crt.d-2+8)%8;k!=(crt.d+3)%8;k = (k+1) % 8){
                int x = crt.x + dx[k];
                int y = crt.y + dy[k];
                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][++Q[(t + newCst) % 3][0].d] = {x,y,d,newCst};
                }
            }
        }
        Q[t][0].d = 0;
        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;
}