Pagini recente » Cod sursa (job #2965014) | Cod sursa (job #1437172) | Cod sursa (job #853727) | Cod sursa (job #1418907) | Cod sursa (job #976153)
Cod sursa(job #976153)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
#define LE 506
struct trei {
int x,y,z;
};
trei que[2][LE*LE*60];
trei que2[LE*LE*60];
int dp[LE][LE][8];
int nr[2],xi,yi,xf,yf;
int result;
int xx[]= {-1,-1, 0, 1,1, 1, 0,-1};
int yy[]= { 0 ,1 ,1, 1,0,-1,-1,-1};
trei mk3(int i1,int i2,int i3) {
trei res;
res.x=i1,res.y=i2,res.z=i3;
return res;
}
void dij() {
bool okz=false;
trei P;
for(int l=0; nr[l]&&okz==false; l^=1) {
int nr2=0;
for(int i=1; i<=nr[l]&&okz==false; ++i) {
P=que[l][i];
//cout<<P.x<<" "<<P.y<<" "<<P.z<<'\n';
if (P.x==xf&&P.y==yf) {
result=dp[P.x][P.y][P.z];
okz=true;
continue;
}
if (dp[P.x][P.y][(P.z+8-1)%8]==0)
que2[++nr2]=mk3(P.x,P.y,(P.z+8-1)%8);
if (dp[P.x][P.y][(P.z+1)%8]==0)
que2[++nr2]=mk3(P.x,P.y,(P.z+1)%8);
if(dp[P.x+xx[P.z]][P.y+yy[P.z]][P.z]==0) {
dp[P.x+xx[P.z]][P.y+yy[P.z]][P.z]=dp[P.x][P.y][P.z];
que[l][++nr[l]]=mk3(P.x+xx[P.z],P.y+yy[P.z],P.z);
}
}
for(int i=1; i<=nr2; ++i)
if (dp[que2[i].x][que2[i].y][que2[i].z]==0){
que[l^1][++nr[l^1]]=que2[i];
dp[que2[i].x][que2[i].y][que2[i].z]=dp[P.x][P.y][P.z]+1;
}
nr[l]=0;
}
}
int n,m,i,j;
short int a[LE][LE];
int main() {
f>>n>>m;
f>>xi>>yi>>xf>>yf;
for(i=1; i<=n; ++i)
for(j=1; j<=m; ++j) f>>a[i][j];
for(i=0; i<=7; ++i) {
que[0][++nr[0]]=mk3(xi,yi,i);
dp[xi][yi][i]=1;
// cout<<xi<<" "<<yi<<" "<<i<<'\n';
}
for(i=0; i<=n+1; ++i)
for(j=0; j<=m+1; ++j)
for(int k=0; k<=7; ++k)
if (i==0||i==n+1||j==0||j==m+1||a[i][j]==1)
dp[i][j][k]=-1;
dij();
// cout<<result-1<<'\n';
g<<result-1<<'\n';
f.close();
g.close();
return 0;
}