Pagini recente » Cod sursa (job #3128761) | Cod sursa (job #1876476) | Cod sursa (job #1818459) | Cod sursa (job #823736) | Cod sursa (job #28764)
Cod sursa(job #28764)
#include<stdio.h>
#define maxN 500
#define inf 10000
int a[maxN][maxN],d[maxN][maxN],viz[maxN][maxN],si,sj,fi,fj,n,m;
int dir[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
long int c[maxN][maxN];
void citeste()
{freopen("car.in","r",stdin);
scanf("%d %d\n",&n,&m);
scanf("%d %d %d %d\n",&si,&sj,&fi,&fj);
int i,j;
for(i=1;i<=n;i++)
{ for(j=1;j<=m;j++) {scanf("%d ",&a[i][j]); c[i][j]=inf; }
scanf("\n");
}
}
void lee()
{int rot,ii,jj,t,Q[250000][2];
long int cap,coada;
cap=coada=1;
Q[cap][0]=si;
Q[cap][1]=sj;
c[si][sj]=d[si][sj]=0;
for(t=0;t<=7;t++)
{ii=si+dir[t][0];
jj=si+dir[t][1];
if(!a[ii][jj] && ii<n+1 && ii>0 && jj<m+1&& jj>0)
{if(t<4) d[ii][jj]=t+4;
else d[ii][jj]=t-4;
Q[++coada][0]=ii;
Q[coada][1]=jj;
c[ii][jj]=0;
viz[ii][jj]=1;
}
}
viz[si][sj]=1;
cap++;
while (cap<=coada)
{for(t=0;t<=7;t++)
{rot=(d[ Q[cap][0] ][ Q[cap][1] ]+t)%8;
ii=Q[cap][0]+dir[ rot ][0];
jj=Q[cap][1]+dir[ rot ][1];
if(!a[ii][jj] && ii<n+1 && ii>0 && jj<m+1&& jj>0)
{if(!viz[ii][jj]){Q[++coada][0]=ii; Q[coada][1]=jj; viz[ii][jj]=1;}
if(t==0 && c[Q[cap][0]][Q[cap][1]]+4<c[ii][jj]) {c[ii][jj]=c[Q[cap][0]][Q[cap][1]]+4;
if(rot<4) d[ii][jj]=rot+4;
else d[ii][jj]=rot-4;
}
if((t==1 ||t==7) && c[Q[cap][0]][Q[cap][1]]+3<c[ii][jj]) {c[ii][jj]=c[Q[cap][0]][Q[cap][1]]+3;
if(rot<4) d[ii][jj]=rot+4;
else d[ii][jj]=rot-4;
}
if((t==2 ||t==6) && c[Q[cap][0]][Q[cap][1]]+2<c[ii][jj]) {c[ii][jj]=c[Q[cap][0]][Q[cap][1]]+2;
if(rot<4) d[ii][jj]=rot+4;
else d[ii][jj]=rot-4;
}
if((t==3 ||t==5) && c[Q[cap][0]][Q[cap][1]]+1<c[ii][jj]) {c[ii][jj]=c[Q[cap][0]][Q[cap][1]]+1;
if(rot<4) d[ii][jj]=rot+4;
else d[ii][jj]=rot-4;
}
if(t==4 && c[Q[cap][0]][Q[cap][1]]<c[ii][jj]) {c[ii][jj]=c[Q[cap][0]][Q[cap][1]];
if(rot<4) d[ii][jj]=rot+4;
else d[ii][jj]=rot-4;
}
}
}
cap++;
}
}
int main ()
{int i;
citeste();
for(i=0;i<=n;i++) {a[i][0]=1; a[i][m+1]=1;}
for(i=0;i<=m;i++) {a[0][i]=1; a[n+1][i]=1;}
lee();
freopen("car.out","w",stdout);
printf("%ld\n",c[fi][fj]);
return 0;
}