Pagini recente » Cod sursa (job #2646811) | Cod sursa (job #3128186) | Cod sursa (job #1824670) | Cod sursa (job #1123377) | Cod sursa (job #976141)
Cod sursa(job #976141)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
#define LE 706
struct trei {
int x,y,z;
};
trei que[2][LE*LE*60];
int dp[LE][LE][8];
bool viz[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;
for(int l=0; nr[l]&&okz==false; l^=1) {
for(int i=1; i<=nr[l]&&okz==false; ++i) {
trei 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) {
// dp[P.x][P.y][(P.z+8-1)%8]=dp[P.x][P.y][P.z]+1;
// que[l^1][++nr[l^1]]=mk3(P.x,P.y,(P.z+8-1)%8);
// }
if (dp[P.x][P.y][(P.z+1)%8]==0) {
dp[P.x][P.y][(P.z+1)%8]=dp[P.x][P.y][P.z]+1;
que[l^1][++nr[l^1]]=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);
}
}
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;
}