Cod sursa(job #1987940)

Utilizator giotoPopescu Ioan gioto Data 1 iunie 2017 16:05:48
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

int n, m, l1, c1, l2, c2, a[505][505], t[505][505][8], st[3], dr[3];
int q[3][1000005];
struct coada{
    int l, c, d;
}z;
short dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
short dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
inline int cost(int d1, int d2){
    int dif = abs(d2 - d1);
    return min(8 - dif, dif);
}
inline void bfs(){
    st[0] = st[1] = st[2] = 1; dr[0] = 0;
    int k = 0;
    for(short kr = 0; kr < 8 ; ++kr){
        if(a[l1 + dx[kr]][c1 + dy[kr]] == 1) continue ;
        t[l1][c1][kr] = 0;
        q[0][++dr[k]] = (l1 << 9) + c1 + (kr << 18);
    }
    while(st[0] <= dr[0] || st[1] <= dr[1] || st[2] <= dr[2]){
        while(st[k] > dr[k])
            k = (k + 1) % 3;
        int x = q[k][st[k]++];
        z.d = x >> 18;
        z.c = (x & 511); z.l = (x >> 9) & 511;
        short cr = z.d, steps = 0;
        while(steps <= 2){
            short l = dx[cr] + z.l;
            short c = dy[cr] + z.c;
            int usu = cost(cr, z.d);
            if(l >= 1 && c >= 1 && l <= n && c <= m && a[l][c] == 0){
                if(t[l][c][cr] > t[z.l][z.c][z.d] + usu){
                    t[l][c][cr] = t[z.l][z.c][z.d] + usu;
                    if(l == l2 && c == c2)
                        break ;
                    int newk = (k + usu) % 3;
                    q[newk][++dr[newk]] = (l << 9) + c + (cr << 18);
                }
            }
            ++steps; ++cr;
            if(cr == 8) cr = 0;
        }
        cr = z.d - 1; steps = 0;
        while(steps <= 1){
            short l = dx[cr] + z.l;
            short c = dy[cr] + z.c;
            if(l >= 1 && c >= 1 && l <= n && c <= m && a[l][c] == 0){
                int usu = cost(cr, z.d);
                if(t[l][c][cr] > t[z.l][z.c][z.d] + usu){
                    t[l][c][cr] = t[z.l][z.c][z.d] + usu;
                    if(l == l2 && c == c2)
                        break ;
                    int newk = (k + usu) % 3;
                    q[newk][++dr[newk]] = (l << 9) + c + (cr << 18);
                }
            }
            ++steps; --cr;
            if(cr < 0) cr = 7;
        }
    }
}
int main()
{
    freopen("car.in", "r", stdin);
    freopen("car.out", "w", stdout);
    scanf("%d%d", &n, &m);
    scanf("%d%d%d%d", &l1, &c1, &l2, &c2);
    for(int i = 1; i <= n ; ++i)
        for(int j = 1; j <= m ; ++j){
            scanf("%d", &a[i][j]);
            for(short k = 0; k < 8 ; ++k)
            t[i][j][k] = 2000000000;
        }
    bfs();
    int Sol = 2000000000;
    for(short k = 0; k < 8 ; ++k)
        Sol = min(Sol, t[l2][c2][k]);
    if(Sol == 2000000000) printf("-1");
    else printf("%d", Sol);
    return 0;
}