Cod sursa(job #1987921)

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

int n, m, l1, c1, l2, c2, a[505][505], t[505][505], st[5], dr[5];
struct coada{
    int l, c, d;
}q[5][1000005], 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){
    if(d2 == -1) return 0;
    int dif = abs(d2 - d1);
    if(dif <= 4) return dif;
    else return 8 - dif;
}
inline void bfs(){
    st[0] = st[1] = st[2] = st[3] = st[4] = 1; dr[0] = 1;
    int k = 0;
    t[l1][c1] = 0;
    q[0][1].l = l1; q[0][1].c = c1; q[0][1].d = -1;
    while(st[0] <= dr[0] || st[1] <= dr[1] || st[2] <= dr[2] || st[3] <= dr[3] || st[4] <= dr[4]){
        while(st[k] > dr[k])
            k = (k + 1) % 5;
        z = q[k][st[k]++];
        for(short cr = 0; cr < 8 ; ++cr){
            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] > t[z.l][z.c] + usu){
                    t[l][c] = t[z.l][z.c] + usu;
                    if(z.l == l2 && z.c == c2) break ;
                    int newk = (k + usu) % 5;
                    q[newk][++dr[newk]].l = l;
                    q[newk][dr[newk]].c = c;
                    q[newk][dr[newk]].d = cr;
                }
            }

        }
    }
}
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]), t[i][j] = 2000000000;
    bfs();
    printf("%d", t[l2][c2]);
    return 0;
}