문제

꽁꽁 얼어붙은 한강 위로 고양이가 걸어 다니고 있다.

한강은 가로 칸, 세로 칸인 직사각형 형태이며, 꽁꽁 얼어붙은 칸과 녹은 칸으로 이루어져 있다. 상하좌우로 붙어 있는 꽁꽁 얼어붙은 칸에서는 자유롭게 걸어다닐 수 있지만, 녹은 칸 위로는 걸어다닐 수 없다.

고양이는 점프를 통해 상하좌우로 인접한 한 칸을 뛰어넘어 총 두 칸 이동할 수 있으며, 뛰어넘는 칸은 녹은 칸이어도 상관없다. 하지만 고양이는 점프하기가 너무 귀찮았던 나머지 당신에게 도움을 요청했다.

왼쪽에서 번째, 위에서 번째 칸을 로 쓰자. 고양이는 에서 로 가려 한다. 단, 점프는 귀찮기 때문에 최대한 적게 점프하며 이동할 것이다. 귀여운 고양이를 위해 에서 로 이동하기 위한 최소 점프 횟수를 구해주자.

입력

첫째 줄에 한강의 크기를 나타내는 두 정수 , 이 공백으로 구분되어 주어진다.

다음 줄부터 한강의 상태가 개 줄에 걸쳐 주어진다. 각각의 줄은 개 문자로 이루어져 있으며, 각 문자는 얼어붙은 칸을 나타내는 O 또는 녹은 칸을 나타내는 X 중 하나이다.

다음 줄에 출발 칸과 도착 칸을 나타내는 네 정수 , , , 가 공백으로 구분되어 주어진다.

출발 칸과 도착 칸은 항상 얼어붙어 있다.

출력

첫째 줄에 에서 로 이동하기 위한 최소 점프 횟수를 출력한다.

만약 에서 로 이동할 수 없다면 -1을 출력한다.

노트

https://youtube.com/shorts/mZPkoLfdGQg?si=I0jKVOYSp8X10pBU 를 보면 도움이 될 수도 있다.

예제 해설

첫째 예제에서, 처럼 점프를 번 수행한 뒤 에서 로 걸어서 이동할 수 있다. 과 는 대각선으로만 붙어 있으므로 바로 이동할 수 없으며, 상하좌우 방향도 아니니 점프도 할 수 없다.