Pagini recente » Cod sursa (job #1708432) | Cod sursa (job #1745785) | Cod sursa (job #459527) | Cod sursa (job #1927083) | Cod sursa (job #2670691)
#include <bits/stdc++.h>
#define INF 1000000005
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
int din[501][501][8];
int dl[]={-1,-1,0,1,1,1,0,-1};
int dc[]={0,1,1,1,0,-1,-1,-1};
int cost[8][8],x2,y2,i,j,n,m,k,xcur,ycur;
int ok[501][501];
struct wow
{
int x,y,dir;
};
bool interior (int x,int y)
{
if (1<=x&&x<=n&&1<=y&&y<=m)
{
if (ok[x][y]==0)
{
return 1;
}
}
return 0;
}
bool verif ()
{
int i;
for (i=0;i<=7;i++)
{
if (din[x2][y2][i]!=INF)
{
return 1;
}
}
return 0;
}
int x,y;
queue <wow> q;
int main()
{
f>>n>>m;
f>>x>>y>>x2>>y2;
for (int i=0;i<8;i++){
for (int j=0;j<8;j++){
cost[i][j] = min(abs(j-i), 8 - max(i,j) + min(i,j));
}
}
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++)
{
f>>ok[i][j];
}
}
if (ok[x][y]==1||ok[x2][y2]==1)
{
g<<"-1";
return 0;
}
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++)
{
for (k=0;k<=7;k++)
{
din[i][j][k]=INF;
}
}
}
for (i=0;i<=7;i++)
{
din[x][y][i]=0;
xcur=x+dl[i];
ycur=y+dc[i];
if (interior(xcur,ycur)==1)
{
din[xcur][ycur][i]=0;
q.push(wow{xcur,ycur,i});
}
}
int minim=INF;
while (!q.empty())
{
wow acum=q.front();
q.pop();
if (acum.x==x2&&acum.y==y2)
{
minim=min(minim,din[acum.x][acum.y][acum.dir]);
}
else
{
if (din[acum.x][acum.y][acum.dir]<minim)
{
for (i=0;i<=7;i++)
{
xcur=acum.x+dl[i];
ycur=acum.y+dc[i];
if (interior(xcur,ycur)==1&&din[xcur][ycur][i]>din[acum.x][acum.y][acum.dir]+cost[acum.dir][i]&&cost[acum.dir][i]!=4)
{
din[xcur][ycur][i]=din[acum.x][acum.y][acum.dir]+cost[acum.dir][i];
q.push(wow{xcur,ycur,i});
}
}
}
}
}
if (minim==INF)
{
g<<"-1"<<'\n';
return 0;
}
g<<minim;
return 0;
}