Cod sursa(job #1800838)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 8 noiembrie 2016 10:41:00
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 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;
char a[Nmax][Nmax];
queue<int> q[3];

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

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

    int x, y, new_node;

    x = node&X; x>>=12;
    y = node&Y; y>>=3;

         if(dir==0) --x;
    else if(dir==1) --x, ++y;
    else if(dir==2) ++y;
    else if(dir==3) ++x, ++y;
    else if(dir==4) ++x;
    else if(dir==5) ++x, --y;
    else if(dir==6) --y;
    else if(dir==7) --x, --y;

    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[(act+cost)%3].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<=n+1; ++i)
    for(j=0; j<=m+1; ++j)
    if(i==0 || j==0 || i==n+1 || j==m+1) a[i][j] = '1';
    else scanf("%c ", &a[i][j]);

    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;
            go(node, dir, 0);
            go(node, dir-1, 1);
            go(node, dir+1, 1);
            go(node, dir-2, 2);
            go(node, 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;
}