시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 436 99 76 30.400%

문제

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

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

빙판길은 크기가 n×m인 직사각형 격자모양이고, 빙판길 각 칸의 얼음은 이미 손상되어 있거나, 손상되지 않은 상태이다.

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

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

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

(a) (b)

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

그리고 (r2, c2) 에 위치한 올라프가 만든 탈출구는 빙판길 밑에 있기 때문에 (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를 출력한다.

예제 입력 1

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

예제 출력 1

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

출처

University > 서강대학교 > 2015 Sogang Programming Contest - Master D번

University > 서강대학교 > 2015 Sogang Programming Contest - Champion C번