시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 365 52 50 26.455%

문제

겨울왕국의 올라프의 유일한 후손인 선진이는 현재 엘사가 얼려놓은 빙판길 위에 서 있다.

빙판길은 n×m의 크기를 갖는 직사각형 격자모양이고, 빙판길의 각 칸은 손상되거나 손상되지 않은 상태이다. (손상된 칸은 영대문자 X로, 손상되지 않은 칸은 . 으로 주어진다.)

그리고 직사각형의 행을 위에서부터 1부터 n까지로, 열을 왼쪽에서부터 오른쪽으로까지 1부터 m이라 가정한다.

빙판길에서 손상된 칸으로 이동을 하면 빙판길 아래로 추락하여 선진이가 동사하기 때문에, 각 칸에서 인접하면서 손상되지 않은 얼음이 있는 칸으로만 이동할 수 있다.

그리고 빙판의 상태가 약하기 때문에, 현재위치에서 다른칸으로 이동을 하면 선진이의 무게 때문에 이동하기 전 위치의 칸은 손상된 상태로 바뀌게 된다.

(a) (b)

예를 들면, 위의 (a)와 같은 상태에서 (1, 1)에 선진이가 서 있을 때 선진이가 오른쪽으로 한 칸 이동하면 선진이의 위치는 (1, 2)가 되고, 빙판길의 상태는 (b)와 같이 변한다.

하지만, 직사각형 어떤 (r2 ,c2) 위치에서는 올라프가 만들어놓은 탈출구가 있어서 이 위치를 통해서만 손상되어 있는 상태의 얼음을 밟아 추락해도 선진이가 살아남을수가 있다 .

선진이가 있는 빙판길의 상태가 주어지고, 시작 위치 (r1, c1)와  탈출구가 있는 지점 (r2, c2)가 주어졌을 때 선진이가 올라프가 만들어 놓은 탈출구를 통해 탈출이 가능한지 여부를 판단하는 프로그램을 작성하시오 

입력

첫 번째 줄은  두 개의 정수 n, m (1 ≤ n, m ≤ 500)이 주어진다. n은 격자에서 행의 수를 의미하고, m은 열의 갯수를 의미한다.

다음 n개의 줄에는 각각 m개의 문자로 이루어진 빙판길의 초기 상태가 주어진다. (손상된 얼음이면 'X'로 표시되고, 손상되지 않은 얼음은 '.' 으로 표시된다.)

다음 줄은 두개의 정수 r1과 c1 (1 ≤ r1 ≤ n, 1 ≤ c1 ≤ m)이 주어진다. 이는 선진이의 초기위치를 나타낸다. 항상 초기위치의 빙판길의 상태는 ‘X’로 주어진다.

다음 줄은 두개의 정수 r2과 c2 (1 ≤ r2 ≤ n, 1 ≤ c2 ≤ m)가 주어진다. 이는 올라프가 만들어 놓은 탈출구의 위치를 나타내며, 초기 위치와 일치할 수도 있다.

출력

선진이가 탈출 할 수 있다면, YES를 출력하고 아니라면 NO를 출력한다.

예제 입력

4 6
X...XX
...XX.
.X..X.
......
1 6
2 2

예제 출력

YES

예제 입력 2

5 4
.X..
...X
X.X.
....
.XX.
5 3
1 1

예제 출력 2

NO

예제 입력 3

4 7
..X.XX.
.XX..X.
X...X..
X......
2 2 
1 6

예제 출력 3

YES

예제 입력 4

1 1
X
1 1
1 1

예제 출력 4

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) 의 순서로 가면 탈출이 가능하다.