#include <fstream>
#include <stack>
#include <array>
#include <vector>
#include <tuple>
#include <limits>
#include <utility>
#include <string>
#include <iostream>
using namespace std;
constexpr int dx[] = {0, 1, 1, 1, 0, -1, -1, -1},
dy[] = {1, 1, 0, -1, -1, -1, 0, 1},
gol = numeric_limits<int>::max(), bloc = -4;
class mat{
vector<array<int, 8> > v;
int n, m;
public:
mat(const int N, const int M):
v(N*M),
n(N),
m(M){}
void resize(const int N, const int M){
v.resize(N*M);
n = N;
m = M; }
int& operator[](const tuple<int, int, int>& p){
return v[get<0>(p) * m + get<1>(p)][get<2>(p)]; }
int& la(const int a, const int b, const int c){
return v[a * m + b][c]; }
void print(){
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
cout << "(";
for(int k = 0; k < 8; ++k){
switch(la(i, j, k)){
case gol:
cout << "g ";
break;
case bloc:
cout << "b ";
break;
default:
cout << la(i, j, k) << ' ';
break; } }
cout << ") "; }
cout << '\n'; } }
void edge(const int val){
for(int i = 0; i < n; ++i){
for(int k = 0; k < 8; ++k){
la(i, 0, k) = val;
la(i, m-1, k) = val; } }
for(int i = 0; i < m; ++i){
for(int k = 0; k < 8; ++k){
la(0, i, k) = val;
la(m-1, i, k) = val; } } } };
int delta_unghi(const int a, const int b){
return (a < b) ? min(b-a, 8-b+a) : min(a-b, 8-a+b); }
using coord = tuple<int, int, int>;
class mypq{
vector<stack<coord> > v;
int cur = 0;
void clear(){
while(cur < v.size() && v[cur].empty()){
++cur; } }
public:
void resize(const int sz){
v.resize(sz); }
pair<coord, int> top(){
clear();
return make_pair(v[cur].top(), cur); }
bool empty(){
clear();
return cur == v.size(); }
void pop(){
clear();
v[cur].pop(); }
void push(const pair<coord, int>& p){
v[p.second].push(p.first); }
void emplace(const coord a, const int b){
v[b].push(a); } };
void citeste_date(mat& harta, mypq& de_viz, int& finl, int& finc){
ifstream f("car.in");
int n, m, stl, stc;
f >> n >> m >> stl >> stc >> finl >> finc >> ws;
harta.resize(n+2, m+2);
harta.edge(bloc);
de_viz.resize(4*n*m + 1);
for(int i = 0; i < 8; ++i){
de_viz.emplace(make_tuple(stl, stc, i), 0); }
string buf(2*m, 0);
for(int i = 0; i < n; ++i){
f.read(&buf[0], 2*m);
for(int j = 0; j < m; ++j){
switch(buf[2*j]){
case '0':
for(int k = 0; k < 8; ++k){
harta.la(i+1, j+1, k) = gol; }
break;
case '1':
for(int k = 0; k < 8; ++k){
harta.la(i+1, j+1, k) = bloc; }
break; } } }
for(int i = 0; i < 8; ++i){
harta.la(stl, stc, i) = 0; } }
void fa_dijkstra(mat& harta, mypq& de_viz, const int finl, const int finc){
pair<coord, int> cur, next;
while(!de_viz.empty()){
cur = de_viz.top();
de_viz.pop();
if(get<0>(cur.first) == finl && get<1>(cur.first) == finc){
return; }
if(harta[cur.first] == cur.second){
for(int i = 0; i < 8; ++i){
next.first = make_tuple(
get<0>(cur.first) + dx[i],
get<1>(cur.first) + dy[i],
i);
next.second = cur.second + delta_unghi(get<2>(cur.first), i);
if(harta[next.first] != bloc &&
harta[next.first] > next.second){
harta[next.first] = next.second;
de_viz.push(next); } } } } }
int main(){
mat harta(0, 0);
mypq de_viz;
int finl, finc;
citeste_date(harta, de_viz, finl, finc);
fa_dijkstra(harta, de_viz, finl, finc);
harta.print();
ofstream g("car.out");
int rez = gol;
for(int i = 0; i < 8; ++i){
if(harta.la(finl, finc, i) != bloc){
rez = min(rez, harta.la(finl, finc, i)); } }
g << (rez == gol ? -1 : rez) << '\n';
return 0; }