Cod sursa(job #440586)

Utilizator s_holmesSherlock Holmes s_holmes Data 12 aprilie 2010 11:12:19
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.9 kb
#include <cstdio>

using namespace std;

#define Nmax 512

const int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int n, m, xf, yf, xs, ys;
int 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]);
}

bool cond(int x, int y)
{
    return (x > 0 && x <= n && y > 0 && y <= m);
}

void solve()
{
    int i, 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 (cond(ii, jj) && !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) % 9; if (dir == 8) dir = 0;
                ii = i;
                jj = j;
                poz = (ii << 12) + (jj << 3) + dir;
                if (cond(ii, jj) && !a[ii][jj])
                    if (viz[poz] == 0)
                    {
                        viz[poz] = 1;
                        min[poz] = min[nr] + 1;
                        v[p2][++l[p2]] = poz;
                    }       
               
                //miscare trigonometrica
                dir = dir-2; if (dir == -1) dir = 7;
                ii = i;
                jj = j;
                poz = (ii << 12) + (jj << 3) + dir;
                if (cond(ii, jj) && !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;
    }
}

int main()
{
    readdata();
    solve();
    printf("%d\n", rez-1);
    return 0;
}