Pagini recente » Cod sursa (job #960129) | Cod sursa (job #1686471) | Cod sursa (job #1958844) | Cod sursa (job #2047872) | Cod sursa (job #441712)
Cod sursa(job #441712)
// 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;
}