Cod sursa(job #1987928)

Utilizator giotoPopescu Ioan gioto Data 1 iunie 2017 15:37:22
Problema Car Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 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[5], dr[5];
struct coada{
    int l, c, d, cost;
}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;
    for(short k = 0; k < 8 ; ++k)
    t[l1][c1][k] = 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][cr] > z.cost + usu){
                    t[l][c][cr] = z.cost + usu;
                    if(l == l2 && 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;
                    q[newk][dr[newk]].cost = t[l][c][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]);
            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]);
    printf("%d", Sol);
    return 0;
}