Cod sursa(job #1800860)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 8 noiembrie 2016 11:01:38
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <bits/stdc++.h>

using namespace std;

const int X = 511<<12, Y = 511<<3, Dir = 7;

const int inf = 1e9;
const int Nmax = 505;

int xi, yi, xf, yf, dir, n, m, node, ans, act, d[1<<21], i, j, dist, x, y, mod[7];
char a[Nmax][Nmax], ch[Nmax];
queue<int> q[3];

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


inline int make_node(int x, int y, int dir)
{
    x <<= 12;
    y <<= 3;
    return x|y|dir;
}

inline void go(int x, int y, int dir, int cost)
{
    if(dir<0) dir += 8;
    else if(dir>7) dir -= 8;

    int new_node;

    x += dx[dir], y += dy[dir];

    if(a[x][y]=='1') return;

    new_node = make_node(x, y, dir);
    if(d[new_node] > d[node] + cost)
    {
        d[new_node] = d[node] + cost;
        q[mod[act+cost]].push(new_node);
    }
}

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

    scanf("%d %d\n", &n, &m);
    scanf("%d %d %d %d\n", &xi, &yi, &xf, &yf);

    for(i=0; i<=4; ++i) mod[i] = i%3;

    for(i=1; i<=n; ++i)
    {
        gets(ch+1);
        for(j=1; j<=m; ++j) a[i][j] = ch[2*j-1];
        a[i][0] = a[i][m+1] = '1';
    }

    memset(a[0], '1', sizeof(a[0]));
    memset(a[n+1], '1', sizeof(a[0]));

    for(i=0; i<(1<<21); ++i) d[i] = inf;

    dist = 0;

    for(i=0; i<8; ++i)
    {
        node = make_node(xi, yi, i);
        q[0].push(node);
        d[node] = 0;
    }

    act = 0;
    while(q[0].size() + q[1].size() + q[2].size() > 0)
    {
        while(q[act].size())
        {
            node = q[act].front();
            q[act].pop();
            if(d[node] < dist) continue;

            dir = node&Dir;
            x = node&X, x>>=12;
            y = node&Y, y>>=3;

            go(x, y, dir, 0);
            go(x, y, dir-1, 1);
            go(x, y, dir+1, 1);
            go(x, y, dir-2, 2);
            go(x, y, dir+2, 2);
        }

        ++act;
        if(act==3) act=0;
        ++dist;
    }

    ans = inf;
    for(i=0; i<8; ++i)
    {
        node = make_node(xf, yf, i);
        ans = min(ans, d[node]);
    }

    printf("%d\n", ans==inf ? -1 : ans);

    return 0;
}