Pagini recente » Cod sursa (job #332921) | Cod sursa (job #8767) | Cod sursa (job #529417) | Cod sursa (job #2265313) | Cod sursa (job #2670675)
#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;
bool 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 (i=0;i<=7;i++)
{
cost[i][i]=0;
}
cost[0][1]=3;cost[0][2]=2;cost[0][3]=1;cost[0][4]=4;cost[0][5]=1;cost[0][6]=2;cost[0][7]=3;
cost[1][2]=3;cost[1][3]=2;cost[1][4]=1;cost[1][5]=4;cost[1][6]=1;cost[1][7]=2;
cost[2][3]=3;cost[2][4]=2;cost[2][5]=1;cost[2][6]=4;cost[2][7]=1;
cost[3][4]=3;cost[3][5]=2;cost[3][6]=1;cost[3][7]=4;
cost[4][5]=3;cost[4][6]=2;cost[4][7]=1;
cost[5][6]=3;cost[5][7]=2;
cost[6][7]=3;
for (i=0;i<=7;i++)
{
for (j=i+1;j<=7;j++)
{
cost[j][i]=cost[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++)
{
xcur=x+dl[i];
ycur=y+dc[i];
if (interior(xcur,ycur)==1)
{
din[xcur][ycur][i]=0;
q.push(wow{xcur,ycur,i});
}
}
while (!q.empty()&&verif()==0)
{
wow acum=q.front();
q.pop();
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])
{
din[xcur][ycur][i]=din[acum.x][acum.y][acum.dir]+cost[acum.dir][i];
q.push(wow{xcur,ycur,i});
}
}
}
if (verif()==0)
{
g<<"-1"<<'\n';
return 0;
}
int minim=INF;
for (j=0;j<=7;j++)
{
if (din[x2][y2][j]<minim)
{
minim=din[x2][y2][j];
}
}
g<<minim;
return 0;
}