선진이의 겨울 왕국

떠난 칸이 부서지는 격자에서 시작 칸에서 출발해 해치 칸을 밟고 떠났다가 다시 밟을 수 있는지 판정합니다.

어려움8DFS그래프아직 제출이 없습니다시간 제한2초메모리 제한256 MB

문제

겨울 왕국에 나오는 올라프의 하나뿐인 후손 선진이는 엘사가 얼려 놓은 빙판길 위에 서 있다.

빙판길은 n×mn \times m 크기의 직사각형 격자이고, 각 칸의 얼음은 손상된 상태이거나 손상되지 않은 상태이다. 손상된 칸은 영문 대문자 X, 손상되지 않은 칸은 .으로 주어진다. 행 번호는 위에서부터 1번에서 nn번까지, 열 번호는 왼쪽에서부터 1번에서 mm번까지 매긴다.

선진이가 손상된 칸으로 이동하면 빙판 아래로 추락해 얼어 죽는다. 그래서 상하좌우로 인접하면서 손상되지 않은 칸으로만 이동해야 한다. 빙판이 약해서, 선진이가 다른 칸으로 이동하면 방금 떠난 칸의 얼음이 손상된 상태로 바뀐다.

(a)(b)

예를 들어 그림 (a)처럼 (1,1)(1, 1)에 서 있던 선진이가 그림 (b)처럼 오른쪽으로 한 칸 이동하면 위치는 (1,2)(1, 2)가 되고, (1,1)(1, 1)의 얼음은 손상되어 다시 지나갈 수 없다.

올라프가 만든 탈출구는 (r2,c2)(r_2, c_2)의 빙판 아래에 있다. 탈출구를 쓰려면 (r2,c2)(r_2, c_2)의 얼음을 손상시킨 다음, 손상된 그 얼음을 다시 밟아 아래로 떨어져야 한다. 탈출구 위의 얼음이 처음부터 손상되어 있을 수도 있다.

빙판길의 초기 상태와 선진이의 시작 위치 (r1,c1)(r_1, c_1), 탈출구의 위치 (r2,c2)(r_2, c_2)가 주어질 때, 선진이가 탈출할 수 있는지 판별하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 nn, mm (1n,m5001 \le n, m \le 500)이 주어진다. nn은 격자의 행 개수, mm은 열 개수이다.

다음 nn개 줄에는 각각 mm개의 문자로 이루어진 빙판길의 초기 상태가 주어진다. 손상된 얼음은 X, 손상되지 않은 얼음은 .이다.

다음 줄에 두 정수 r1r_1, c1c_1 (1r1n1 \le r_1 \le n, 1c1m1 \le c_1 \le m)이 주어진다. 선진이의 시작 위치이며, 이 칸의 상태는 항상 X이다.

다음 줄에 두 정수 r2r_2, c2c_2 (1r2n1 \le r_2 \le n, 1c2m1 \le c_2 \le m)가 주어진다. 올라프가 만든 탈출구의 위치이며, 시작 위치와 같을 수도 있다.

출력

선진이가 탈출할 수 있으면 YES를, 탈출할 수 없으면 NO를 출력한다.

힌트

첫 번째 예제에서는 (1,6)(2,6)(3,6)(4,6)(4,5)(4,4)(4,3)(4,2)(4,1)(3,1)(2,1)(2,2)(2,3)(1,3)(1,2)(2,2)(1, 6) \to (2, 6) \to (3, 6) \to (4, 6) \to (4, 5) \to (4, 4) \to (4, 3) \to (4, 2) \to (4, 1) \to (3, 1) \to (2, 1) \to (2, 2) \to (2, 3) \to (1, 3) \to (1, 2) \to (2, 2) 순서로 이동하면 탈출할 수 있다.