#include <stdio.h>
#include <stdlib.h>
typedef struct mutare{
int i; //cordonata i de pe care se porneste mutarea
int j; //coordonata j de pe care se porneste mutarea
int lmove;
struct MUTARE *next;
struct MUTARE *last;
int score;
} MUTARE;
int n, m, si, sj, fi,fj, s, movecount, score, end;
int matrice[500][500];
MUTARE *first, *last;
int minmoves;
int score;
void read(){
FILE *fp;
fp = fopen("car.in","r");
fscanf(fp,"%d%d%d%d%d%d", &n,&m,&si, &sj, &fi, &fj);
int i, j;
si = si-1; sj = sj-1; fi = fi-1; fj = fj-1;
int p;
for(i = 0; i<n; i++)
for (j = 0; j<m;j++){
fscanf(fp, "%d", &p);
matrice[i][j]=p;
}
fclose(fp);
};
void write(){
if(score ==n*m*3) score = -1;
FILE *fp = fopen("car.out", "w");
fprintf(fp,"%d", score);
fclose(fp);
}
int angle(){
MUTARE *p1, *p2;
p1 = last->last;
p2 = p1->last; //ne imaginam 2 vectori in plan;
int i_exp = p1-> i + (p1->i - p2->i);
int j_exp = p1 -> j + (p1->j - p2->j);
int h1 = last->i - i_exp;
if(h1<0) h1 = 0 - h1;
int h2 = last->j - j_exp;
if(h2<0) h2 = 0 - h2;
//printf("%d", h1+h2);
return h1+h2;
}
int check_legality(int a, int b){ //a si b reprezinta numarul care trebuie adaugat la i si j pt noua mutare
int i = last->i+a, j = last->j+b; // coordonatele casutei verificat
if(matrice[i][j] == 1 || i < 0 || j < 0|| i>=n|| j >=m) {return 0;}
else return 1;
/*MUTARE *p;
p=first;
for(k = 0; k<movecount; k++){
if(p->i == i && p->j ==j) return 0;
if(p!=last)p = p->next;
};*/
}
void move(int a, int b){
// printf("\n {%d, %d} -> {%d, %d} - %d",last->i+1, last->j+1, last->i+a+1, last->j+b+1, last->score);
last->lmove++;
matrice[last->i][last->j] = 1;
MUTARE *p = malloc(s);
p->i = last->i+a;
p->j = last ->j+b;
p->lmove = 0;
p->last= last;
p->next = 0;
last->next = p;
last= p;
movecount++;
p = last->last;
if(movecount >1) last->score = p->score+angle(); else last->score = 0;
}
void move_or_dont(int a, int b){
if(check_legality(a, b)) move(a, b);
else last->lmove++;
}
void start(){
while(!end){
if(last->i==fi&&last->j==fj && last-> score < score) score = last->score;
MUTARE *p ;
if(last->score<score)
switch(last->lmove){
case 0:move_or_dont(-1,0); break;
case 1:move_or_dont(-1,1); break;
case 2:move_or_dont(0,1); break;
case 3:move_or_dont(1,1); break;
case 4:move_or_dont(1,0); break;
case 5:move_or_dont(1,-1); break;
case 6:move_or_dont(0,-1); break;
case 7:move_or_dont(-1,-1); break;
case 8: eighth_move();
break;
} else eighth_move();
}
};
void eighth_move(){
MUTARE *p;
p = last;
if (p==first){end = 1; return;}
else {
last = p->last;
matrice[last->i][last->j] = 0;
// printf("\n {%d, %d} -> {%d, %d}",p->i, p->j, last->i, last->j);
free(p);
last -> next = 0;
movecount--;
}
}
void init_list(){
first = 0;
last = 0;
movecount = 0;
s = sizeof(MUTARE);
first = malloc(s);
first -> i = si;
first -> j = sj;
first -> next = 0;
first -> last = 0;
first -> score = 0;
first->lmove = 0;
last = first;
minmoves = n*m;
score = 3*n*m;
end = 0;
};
int main()
{
read();
init_list();
start();
write();
return 0;
};