Pagini recente » Cod sursa (job #2317541) | Cod sursa (job #3268345) | Cod sursa (job #2457537) | Cod sursa (job #1699836) | Cod sursa (job #400569)
Cod sursa(job #400569)
#include<iostream.h>
#include<fstream.h>
ifstream f("car.in");
ofstream g("car.out");
int x1[10],x2[10],x,y,l1,c1,n,m,xi,xf,yi,yf,dir,w;
int sw[502][502][8],a[502][502];
int l[3][2800000],p[3];
void afisare()
{
int i,min=1000000;
for (i=0;i<8;i++)
if (min>sw[xf][yf][i] && sw[xf][yf][i]>-1)
min=sw[xf][yf][i];
g<<min;
}
void add (int k, int C)
{
int i;
dir=(k>>18);
x= (k>>9) & 511;
y= (k&511);
if (sw[x][y][dir]<C) return ;
for (i=0;i<8;i++)
if (abs(dir-i)<=2 || 8-abs(i-dir)<=2)
{
w=abs(dir-i);
if (w>2) w=8-abs(dir-i);
l1=x+x1[i];
c1=y+x2[i];
if (l1>0 && l1<=n && c1>0 && c1<=m && a[l1][c1]==0 && (sw[l1][c1][i]==-1 || sw[l1][c1][i]>C+w ))
{
sw[l1][c1][i]=C+w;
w=(C+w)%3;
l[w][++l[w][0]]=(i<<18)+(l1<<9)+c1;
}
}
}
void init()
{
int i;
for (i=0;i<8;i++)
{
l[0][++l[0][0]]=(i<<18)+(xi<<9)+yi;
sw[xi][yi][i]=0;
}
}
void compute()
{
init();
int C,c,i;
C=0;
for (i=0;i<8;i++)
sw[xi][yi][i]=0;
while (l[0][0]+l[1][0]+l[2][0]-p[0]-p[1]-p[2]>0)
{
c=C%3;
while (l[c][0]-p[c]>0)
add(l[c][++p[c]],C);
C++;
}
}
void citire()
{
int i,j,k;
f>>n>>m;
f>>xi>>yi>>xf>>yf;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{
for (k=0;k<8;k++)
sw[i][j][k]=-1;
f>>a[i][j];
}
f.close();
x1[0]=-1;x2[0]=0;
x1[1]=-1;x2[1]=1;
x1[2]=0; x2[2]=1;
x1[3]=1;x2[3]=1;
x1[4]=1;x2[4]=0;
x1[5]=1;x2[5]=-1;
x1[6]=0;x2[6]=-1;
x1[7]=x2[7]=-1;
}
int main()
{
citire();
compute();
afisare();
return 0;
}