Pagini recente » Cod sursa (job #1918330) | Cod sursa (job #2064386) | Cod sursa (job #2644331) | Cod sursa (job #2236588) | Cod sursa (job #84746)
Cod sursa(job #84746)
#include <stdio.h>
#include <vector>
using namespace std;
#define Nmax 500
#define Mmax 500
#define Xmax 1 << 21 + 1
int N,M,i,j,cost = 0;
int Sx,Sy,Fx,Fy;
int a[Nmax][Mmax];
int d[Xmax];
int xx[8]={-1,-1,0,1,1,1,0,-1};
int yy[8]={0,-1,-1,-1,0,1,1,1};
vector<int> c[2];
void citire()
{
freopen("car.in","r",stdin);
scanf("%d %d",&N,&M);
scanf("%d %d %d %d",&Sx,&Sy,&Fx,&Fy);
--Sx;--Sy;--Fx;--Fy;
for (i=0;i<N;++i)
for (j=0;j<N;++j)
scanf("%d",&a[i][j]);
fclose(stdin);
}
int expand(int nod)
{
int px,py,dir,aux;
//despachetarea
dir = nod >> 18;
px = (nod >> 9) - (dir << 9) + xx[dir];
py = nod - (dir << 18) - ((px-xx[dir]) << 9) + yy[dir];
// 45 grade la dreapta
if (dir == 0)
if (d[ nod + (7 << 18) ] > d[ nod ] + 1)
{
c[1-(cost & 1)].push_back( nod + (7 << 18) );
d[ nod + (7 << 18) ] = d[ nod ] + 1;
}
else;
else
if (d[ nod - (1 << 18) ] > d[ nod ] + 1)
{
c[1-(cost & 1)].push_back( nod - (1 << 18) );
d[ nod - (1 << 18) ] = d[ nod ] + 1;
}
//45 grade la stanga
if (dir == 7)
if (d[ nod - (7 << 18) ] > d[ nod ] + 1)
{
c[1-(cost & 1)].push_back( nod - (7 << 18) );
d[ nod - (7 << 18) ] = d[ nod ] + 1;
}
else;
else
if (d[ nod + (1 << 18) ] > d[ nod ] + 1)
{
c[1-(cost & 1)].push_back( nod + (1 << 18) );
d[ nod + (1 << 18) ] = d[ nod ] + 1;
}
if ((px < 0) || (py < 0) || (px>=N) || (py>=M)) return 0;
else if ((px == Fx) && (py == Fy)) return 2;
//nodul din directia de mers
aux = (dir << 18) + (px << 9) + py;
if ((d[ aux ] > d[ nod ]) && (a[px][py] == 0))
{
//drept inainte
c[cost & 1].push_back( aux );
d[ aux ] = d[ nod ];
}
return 1;
}
void dijkstra()
{
int P=(Sx << 9) + Sy;
int x, v, r;
memset(d,0x3f,sizeof(d));
for (i=0; i<8; ++i)
{
c[0].push_back( (i << 18) + P );
d[ (i << 18) + P ] = 0;
}
while ( c[0].size()+c[1].size() )
{
r = cost & 1;
while ( c[r].size() )
{
x = c[r][ c[r].size() - 1 ];
c[r].pop_back();
if (expand(x) == 2) return;
}
++cost;
}
}
int main()
{
citire();
dijkstra();
freopen("car.out","w",stdout);
printf("%d",cost);
fclose(stdout);
return 0;
}