Pagini recente » Cod sursa (job #1346814) | Cod sursa (job #551645) | Cod sursa (job #559819) | Cod sursa (job #1533564) | Cod sursa (job #1009807)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;
const int MAX_N=510;
const int INF=1000000000;
const int dx[8]={-1,-1,0,1,1,1,0,-1};
const int dy[8]={0,1,1,1,0,-1,-1,-1};
struct nod {
int x,y,d;
nod() {
x=y=d=0;
}
nod(int a,int b,int c) {
x=a;
y=b;
d=c;
}
};
inline nod turnL(nod a) {
a.d--;
if(a.d==-1) {
a.d=7;
}
return a;
}
inline nod turnR(nod a) {
a.d++;
if(a.d==8) {
a.d=0;
}
return a;
}
inline nod adv(nod a) {
a.x+=dx[a.d];
a.y+=dy[a.d];
return a;
}
int x[MAX_N][MAX_N];
int dr[MAX_N][MAX_N][8];
bool viz[MAX_N][MAX_N][8];
int N,M;
inline bool inborder(nod a) {
return a.x>=1&&a.x<=N&&a.y>=1&&a.y<=M&&!x[a.x][a.y];
}
deque<nod> Q;
void initializare(int x,int y) {
for(int i=1;i<=N;i++) {
for(int j=1;j<=M;j++) {
for(int d=0;d<8;d++) {
dr[i][j][d]=INF;
}
}
}
for(int d=0;d<8;d++) {
dr[x][y][d]=0;
Q.push_back(nod(x,y,d));
}
}
void dijkstra() {
while(!Q.empty() ) {
nod act=Q.front();
int cst=dr[act.x][act.y][act.d];
Q.pop_front();
if(inborder(adv(act))) {
nod next=adv(act);
if(!viz[next.x][next.y][next.d]&&cst<dr[next.x][next.y][next.d]) {
Q.push_front(next);
dr[next.x][next.y][next.d]=cst;
}
}
nod next=turnL(act);
if(!viz[next.x][next.y][next.d]&&cst+1<dr[next.x][next.y][next.d]) {
Q.push_back(next);
dr[next.x][next.y][next.d]=cst+1;
}
next=turnR(act);
if(!viz[next.x][next.y][next.d]&&cst+1<dr[next.x][next.y][next.d]) {
Q.push_back(next);
dr[next.x][next.y][next.d]=cst+1;
}
viz[act.x][act.y][act.d]=true;
}
}
int main() {
freopen("car.in","r",stdin);
freopen("car.out","w",stdout);
scanf("%d%d",&N,&M);
int xs,ys,xf,yf;
scanf("%d%d%d%d",&xs,&ys,&xf,&yf);
for(int i=1;i<=N;i++) {
for(int j=1;j<=M;j++) {
scanf("%d",&x[i][j]);
}
}
initializare(xs,ys);
dijkstra();
int ans=INF;
for(int i=0;i<8;i++) {
ans=min(ans,dr[xf][yf][i]);
}
if(ans==INF) {
printf("-1");
}
else {
printf("%d",ans);
}
return 0;
}