Pagini recente » Cod sursa (job #1726798) | Istoria paginii runda/wellcodesimulareav-9martie/clasament | Cod sursa (job #1728014) | Cod sursa (job #184941) | Cod sursa (job #2634842)
#include<bits/stdc++.h>
using namespace std;
const int NMAX=505;
const int INF=2000000000;
const int dx[]={-1,-1,0,1,1,1,0,-1};
const int dy[]={0,1,1,1,0,-1,-1,-1};
int n,m,Si,Sj,Fi,Fj,ans;
int a[NMAX][NMAX],dp[NMAX][NMAX][10];
struct el{
int x,y,dir,cost;
};
queue<el> q0,q1;
ifstream fin("car.in");
ofstream fout("car.out");
inline bool ok(int i, int j){
if(i<1 || j<1 || i>n || j>m || a[i][j])
return false;
return true;
}
inline void read(){
fin>>n>>m;
fin>>Si>>Sj>>Fi>>Fj;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
fin>>a[i][j];
for(int k=0;k<8;k++)
dp[i][j][k]=INF;
}
for(int k=0;k<8;k++){
el temp;
temp.x=Si,temp.y=Sj;
temp.cost=0;
temp.dir=k;
q0.push(temp);
}
}
inline void dijkstra(){
while(!q0.empty()){
while(!q0.empty()){
el temp=q0.front(),temp1;
q0.pop();
temp1.cost=temp.cost, temp1.dir=temp.dir;
temp1.x=temp.x+dx[temp.dir];
temp1.y=temp.y+dy[temp.dir];
if(ok(temp1.x, temp1.y) && dp[temp1.x][temp1.y][temp1.dir]>temp1.cost){
dp[temp1.x][temp1.y][temp1.dir]=temp1.cost;
q0.push(temp1);
}
temp1.cost++;
temp1.dir=(temp.dir+1)%8;
temp1.x=temp.x;
temp1.y=temp.y;
if(ok(temp1.x, temp1.y) && dp[temp1.x][temp1.y][temp1.dir]>temp1.cost){
q1.push(temp1);
dp[temp1.x][temp1.y][temp1.dir]=temp1.cost;
}
temp1.dir=(temp.dir-1);
if(temp1.dir<0)
temp1.dir=7;
if(ok(temp1.x, temp1.y) && dp[temp1.x][temp1.y][temp1.dir]>temp1.cost){
q1.push(temp1);
dp[temp1.x][temp1.y][temp1.dir]=temp1.cost;
}
}
while(!q1.empty()){
el temp=q1.front();
q1.pop();
q0.push(temp);
}
}
}
inline void print(){
int ans=dp[Fi][Fj][0];
for(int d=1;d<8;d++)
ans=min(ans, dp[Fi][Fj][d]);
if(ans==INF)
fout<<"-1";
else
fout<<ans;
}
int main(){
read();
dijkstra();
print();
return 0;
}