/*
* Problem :: 로봇 / 1726
*
* Kind :: BFS
*
* Insight
* - 필요한 최소 명령 횟수는
* 최소 비용 또는 최단 거리로 생각할 수 있다
* 그러니 BFS 를 사용하면 되겠다
* + 한번 방문한 곳을 또 방문할 필요는 없을 것 같다
* 명령 하나하나가 모두 비용이라고 생각하면
* 로봇의 초기 위치와 방향에서 BFS 를 돌때
* 새롭게 방문하는 위치와 방향이 무조건 최소 비용일 수밖에 없다
* 그러니 재방문을 고려하지 않아도 될 듯 하다
*
* Point
* - 여기서 Node 또는 Point(위에서 말한 '곳') 는
* 위치와 방향을 모두 포함한다
* + 같은 위치에 있더라도 방향이 다르면
* 서로 다른곳이라 생각해야 한다
* # 위치와 방향정보를 함께 고려해주자
*
* - Zero-based Numbering
* 위치가 (1,1) 부터, 방향은 1 부터 시작하는데
* 다루기 쉽게 각각 (0,0), 0 부터 시작하게끔 전처리했다
*
* - BFS 에서 Go k 명령을 구현할 때
* Go 1 명령을 수행한다면 도착할 위치가 공장 밖이거나 궤도가 없다면 Go 1 명령은 불가능하다
* + Go 1 명령이 불가능하다면 Go 2, Go 3 명령도 불가능하다
* 이점을 놓치면 항상 정답보다 값이 작은 오답을 얻게 된다
*/
//
// BOJ
// ver.C++
//
// Created by GGlifer
//
// Open Source
#include <iostream>
#include <queue>
using namespace std;
#define endl '\n'
// Set up : Global Variables
int M, N;
char A[100][100];
struct Point { int y, x, d; };
bool isVisited[100][100][4];
enum Direction { East, West, South, North };
enum Turn { Left, Right };
int D[4][2] = {
// Left, Right
{North, South}, // East
{South, North}, // West
{East, West}, // South
{West, East} // North
};
int dy[4] = {0, 0, +1, -1};
int dx[4] = {+1, -1, 0, 0};
// Set up : Functions Declaration
bool isValid(int y, int x);
int main()
{
// Set up : I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Set up : Input
cin >> M >> N;
for (int i=0; i<M; i++)
for (int j=0; j<N; j++)
cin >> A[i][j];
int sy, sx, sd;
cin >> sy >> sx >> sd;
int ey, ex, ed;
cin >> ey >> ex >> ed;
// Process
sy--, sx--, sd--; /* 시작 위치와 방향 Zero-based Numbering */
ey--, ex--, ed--; /* 종료 위치와 방향 Zero-based Numbering */
queue<Point> que;
isVisited[sy][sx][sd] = true;
que.push({sy, sx, sd});
int ans = -1; /* 명령 수행 횟수 */
while (not(que.empty())) {
ans++;
auto sz = que.size();
while (sz--) {
auto [cy, cx, cd] = que.front();
que.pop();
// Control : Output
/* 출발지점에서 도착지점까지 항상 이동가능 */
if (cy == ey && cx == ex && cd == ed) {
cout << ans << endl;
exit(0);
}
/* Go k */
for (int i=1; i<=3; i++) {
int ny = cy + i*dy[cd];
int nx = cx + i*dx[cd];
/* 위치 (ny,nx) 가 공장 내이고 궤도가 설치되어 있다면 */
if (isValid(ny, nx) && A[ny][nx] == '0') {
if (not(isVisited[ny][nx][cd])) {
isVisited[ny][nx][cd] = true;
que.push({ny, nx, cd});
}
/* 위치 (ny,nx) 가 공장 밖이거나 궤도가 설치되어 있지 않다면 */
} else break;
}
/* Turn dir */
for (int i=0; i<2; i++) {
int nd = D[cd][i];
if (not(isVisited[cy][cx][nd])) {
isVisited[cy][cx][nd] = true;
que.push({cy, cx, nd});
}
}
}
}
}
// Helper Functions
bool isValid(int y, int x)
/* 주어진 좌표 (y,x) 가 유효하면 true 를 반환, 그 외 false 를 반환 */
{
return y >= 0 && y < M && x >= 0 && x < N;
}