Cod sursa(job #902730)

Utilizator otto1Palaga Vicentiu-Octavian otto1 Data 1 martie 2013 16:26:27
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <cstdio>

using namespace std;

#define Nmax 512

const int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1},
          dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int n, m, xf, yf, xs, ys, rez, v[2][512*1024], l[2], min[1<<22];
char a[Nmax][Nmax], viz[1<<22];

void readdata()
{
    freopen("car.in", "r", stdin);
    freopen("car.out", "w", stdout);

    int i, j;

    scanf("%d %d", &n, &m);
    scanf("%d %d %d %d", &xs, &ys, &xf, &yf);
    for (i = 1; i <= n; ++i)
    for (j = 1; j <= m; ++j)
        scanf("%d", &a[i][j]);
}

void solve()
{
    int i, cont, p, p2, j, k, dir, nr, ii, jj, poz;

    for (i = 0; i < 8; ++i)
    {
        poz = i + (ys << 3) + (xs << 12);
        v[0][++l[0]] = poz;
        min[poz] = 1;
        viz[poz] = 1;
    }

    p = 0;
    while (l[p])
    {
        p2 = 1-p;
        for (k = 1; k <= l[p]; ++k)
        if (viz[v[p][k]] == 1)
        {
            nr = v[p][k];
            dir = nr & 7;
            j = (nr & (511 << 3)) >> 3;
            i = (nr & (511 << 12)) >> 12;

            //inainteaza
            ii = i + dx[dir];
            jj = j + dy[dir];
            poz = (ii << 12) + (jj << 3) + dir;
            if (ii > 0 && ii <= n && jj > 0 && jj <= m)
            if (!a[ii][jj])
            if (viz[poz] == 0 || min[poz] > min[nr])
            {
                viz[poz] = 1;
                min[poz] = min[nr];
                v[p][++l[p]] = poz;
            }

            //miscare clokwise
            dir = dir+1; if (dir == 8) dir = 0;
            ii = i;
            jj = j;
            poz = (ii << 12) + (jj << 3) + dir;
            if (ii > 0 && ii <= n && jj > 0 && jj <= m)
            if (!a[ii][jj])
            if (viz[poz] == 0)
            {
                viz[poz] = 1;
                min[poz] = min[nr] + 1;
                v[p2][++l[p2]] = poz;
            }

            //miscare anti-clokwise
            dir = dir-2; if (dir == -1) dir = 7;
            ii = i;
            jj = j;
            poz = (ii << 12) + (jj << 3) + dir;
            if (ii > 0 && ii <= n && jj > 0 && jj <= m)
            if (!a[ii][jj])
            if (viz[poz] == 0)
            {
                viz[poz] = 1;
                min[poz] = min[nr] + 1;
                v[p2][++l[p2]] = poz;
            }

            if (i == xf && j == yf)
            {
                rez = min[nr];
                return;
            }
            viz[nr] = 2;
        }
        l[p] = 0;
        p = p2;
    }
}

void writedata()
{
    printf("%d\n", rez-1);
}

int main()
{
    readdata();
    solve();
    writedata();
    return 0;
}