Pagini recente » Cod sursa (job #795458) | Cod sursa (job #266897)
Cod sursa(job #266897)
#include <stdio.h>
#include <vector>
using namespace std;
#define maxl 510
#define maxval 500010
int n,m,i,j,k,l,p,q,dir,newX,newY;
int a[maxl][maxl];
int x[5],y[5];
int d1[8]={0,-1,-1,-1,0,1,1,1};
int d2[8]={1,1,0,-1,-1,-1,0,1};
int cost[8][8];
int val[maxl][maxl][8];
vector <int> c[maxval];
void expand()
{
for (j=0; j<8; j++)
{
newX=p+d1[j];newY=q+d2[j];
if (!a[newX][newY] &&
(val[newX][newY][j]<0 || val[p][q][dir]+cost[dir][j]<val[newX][newY][j]))
{
val[newX][newY][j]=val[p][q][dir]+cost[j][dir];
c[i+cost[j][dir]].push_back((newX<<9)+newY+(j<<18));
}
}
}
int main()
{
freopen("car.in","r",stdin);
freopen("car.out","w",stdout);
scanf("%d %d",&n,&m);
scanf("%d %d %d %d",&x[1],&y[1],&x[2],&y[2]);
for (i=0; i<=n+1; i++)
for (j=0; j<=m+1; j++)
a[i][j]=1;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
scanf("%d",&a[i][j]);
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
for (k=0; k<8; k++) val[i][j][k]=-1;
for (i=0; i<8; i++)
for (j=0; j<i; j++)
{
k=i-j;
if (k>4) k=cost[i-1][j]-1;
cost[i][j]=k;
cost[8-i-1][8-j-1]=k;
}
for (i=0; i<=7; i++)
{
c[0].push_back((x[1]<<9)+y[1]+(i<<18));
val[x[1]][y[1]][i]=0;
}
for (i=0; i<=maxval; i++)
while (c[i].size()>0)
{
l=c[i].size()-1;
k=c[i][l];
c[i].pop_back();
dir=k>>18;
q=k&511;
p=(k>>9)&511;
if (p==x[2] && q==y[2])
{
printf("%d\n",i);
return 0;
}
expand();
}
printf("-1\n");
return 0;
}