Cod sursa(job #441712)

Utilizator ooctavTuchila Octavian ooctav Data 13 aprilie 2010 10:00:40
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
// car2.cpp : Defines the entry point for the console application.
//

#include <cstdio>
#include <queue>
using namespace std;
const int NMAX = 510;
const int MMAX = 510;
const int lin[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int col[] = {0, 1, 1, 1, 0, -1, -1, -1};
pair<int, int> S, D;
bool a[NMAX][MMAX];
int minim[1 << 22];
bool viz[1 << 22];
int N, M;
int Q[2][NMAX * MMAX * 1<<3];
int rez = 0;

void citire()
{
    scanf("%d%d",&N,&M);
    scanf("%d%d", &S.first, &S.second);
    scanf("%d%d", &D.first, &D.second);
    for(int i = 1 ; i <= N ; i++)
        for(int j = 1 ; j <= M ; j++)
            scanf("%d",&a[i][j]);
}

int cond(int x, int y)
{
	return (x && x <= N && y && y <= M);
}

void rezolva()
{
    int p = 0, p2, poz, dir, nr ;
	int i, j, ii, jj;
    for(int dir = 0 ; dir < 8 ; dir++)
    {
        poz = (S.first << 12) + (S.second << 3) + dir;
        minim[poz] = 1;
		viz[poz] = 1;
        Q[p][++Q[p][0]] = poz;
    }
	
    while(Q[p][0])
    {
        p2 = 1 - p;
        for(int k = 1 ; k <= Q[p][0] ; k++)
		{
			nr = Q[p][k];
			i = nr>>12;
			j = (nr>>3) & 511;
			dir = nr & 7;
			
			ii = i + lin[dir];
			jj = j + col[dir];
			if(cond(ii, jj) && !a[ii][jj])
			{
				poz = (ii<<12) + (jj<<3) + dir;
				if(!minim[poz] || minim[poz] > minim[nr])
				{
					minim[poz] = minim[nr];
					Q[p][++Q[p][0]] = poz;
				}
			}
				
			dir++;if(dir == 8) dir = 0;
			ii = i;
			jj = j;
			if(cond(ii, jj) && !a[ii][jj])
			{
				poz = (ii<<12) + (jj<<3) + dir;
				if(!minim[poz])
				{
					minim[poz] = minim[nr] + 1;
					Q[p2][++Q[p2][0]] = poz;
				}
			}
			
			dir	-= 2; if(dir == -1) dir += 8;				
			ii = i;
			jj = j;
			if(cond(ii, jj) && !a[ii][jj])
			{
				poz = (ii<<12) + (jj<<3) + dir;
				if(!minim[poz])
				{
					minim[poz] = minim[nr] + 1;
					Q[p2][++Q[p2][0]] = poz;
				}
			}
				
			if(i == D.first && j == D.second)
			{
				rez = minim[nr];
				return;
			}
		}
		
		Q[p][0] = 0;
		p = p2;
    }
}

int main()
{
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);
    citire();
    rezolva();
    printf("%d",rez - 1);
    return 0;
}