Pagini recente » Cod sursa (job #188525) | Cod sursa (job #2826774) | Cod sursa (job #1519303) | Cod sursa (job #1145768) | Cod sursa (job #383586)
Cod sursa(job #383586)
#include<cstdio>
#define N 501
#define minn(a,b) ((a<b) ? (a):(b))
bool a[N][N],viz[5][N][N],nod[N][N];
short int coada[5][N*N][2],dir[5][N*N],x1[2],y1[2],nr_nod,nr,n,m;
int u[5],p[5],cost[9][9],dist[5][N][N],minim=(1<<31)-1;
const int dx[]={0,0,-1,1,-1,-1,1,1};
const int dy[]={1,-1,0,0,-1,1,-1,1};
void citire()
{
freopen("car.in","r",stdin);
freopen("car.out","w",stdout);
scanf("%hd%hd%hd%hd%hd%hd",&n,&m,&x1[0],&x1[1],&y1[0],&y1[1]);
for (int i=1; i<=n; ++i)
for (int j=1; j<=m; ++j)
{
scanf("%hd",&a[i][j]);
if (a[i][j])
a[i][j]=0;
else
{
a[i][j]=1;
++nr_nod;
}
}
}
void costuri()
{
for (int i=0; i<=8; ++i)
cost[i][i]=0;
cost[0][5]=cost[0][7]=cost[5][0]=cost[7][0]=cost[1][4]=cost[1][6]=cost[6][1]=cost[4][1]=cost[2][4]=cost[4][2]=cost[2][5]=cost[5][2]=cost[3][6]=cost[6][3]=cost[3][7]=cost[7][3]=1;
cost[0][4]=cost[4][0]=cost[0][6]=cost[6][0]=cost[1][5]=cost[5][1]=cost[1][7]=cost[7][1]=cost[2][6]=cost[6][2]=cost[2][7]=cost[7][2]=cost[3][4]=cost[4][3]=cost[3][5]=cost[5][3]=3;
cost[0][2]=cost[2][0]=cost[0][3]=cost[3][0]=cost[1][2]=cost[2][1]=cost[1][3]=cost[3][1]=cost[4][5]=cost[5][4]=cost[4][6]=cost[6][4]=cost[7][5]=cost[5][7]=cost[6][7]=cost[7][6]=2;
cost[0][1]=cost[1][0]=cost[2][3]=cost[3][2]=cost[4][7]=cost[7][4]=cost[5][6]=cost[6][5];
}
void bfs(short int x0[])
{
short int x[2],y[2];
nod[x0[0]][x0[1]]=true;
++nr;
bool ok=true;
coada[0][u[0]][0]=x0[0];
coada[0][u[0]][1]=x0[1];
dir[0][u[0]++]=8;
viz[0][x0[0]][x0[1]]=true;
while (nr<nr_nod)
{
for (int i=0; i<=4; ++i)
{
ok=false;
while (u[i]!=p[i])
{
ok=true;
x[0]=coada[i][p[i]][0];
x[1]=coada[i][p[i]][1];
int d=dir[i][p[i]++];
for (int j=0; j<=7; ++j)
{
y[0]=x[0]+dx[j];
y[1]=x[1]+dy[j];
if (!a[y[0]][y[1]])
continue;
int q=(cost[d][j]+i)%4;
if (viz[q][y[0]][y[1]])
continue;
coada[q][u[q]][0]=y[0];
coada[q][u[q]][1]=y[1];
viz[q][y[0]][y[1]]=true;
dir[q][u[q]++]=j;
dist[q][y[0]][y[1]]=cost[d][j]+dist[i][x[0]][x[1]];
if (nod[y[0]][y[1]])
continue;
++nr;
nod[y[0]][y[1]]=true;
}
}
}
}
}
void afis()
{
for (int i=0; i<=4; ++i)
if (viz[i][y1[0]][y1[1]])
minim=minn(minim,dist[i][y1[0]][y1[1]]);
printf("%d",minim);
}
int main()
{
citire();
costuri();
bfs(x1);
afis();
return 0;
}