탈옥

시간 제한2초메모리 제한512 MB

요약

'+'와 '*'로 표시된 격자에서 같은 기호의 이웃한 칸으로만 이동할 수 있을 때, 입구 칸에서 출구 칸에 도달할 수 있는지 판정한다.

난이도: 쉬움10점 중 3점
유형: 그래프, BFS, 행렬
정답자: 아직 제출이 없습니다

문제

교도소가 미로 모양으로 지어졌다. 미로는 + 또는 *가 적힌 오두막으로 이루어진다. 두 오두막이 변 하나를 공유하면 서로 이웃한다. + 오두막에 있으면 이웃한 + 오두막으로만 이동할 수 있고, * 오두막에 있으면 이웃한 * 오두막으로만 이동할 수 있다.

미로는 가로 길이가 $L$ , 세로 길이가 $W$ 인 직사각형이다. 오두막의 위치는 가로 좌표와 세로 좌표로 나타낸다. 가로 좌표는 왼쪽에서부터 $1$ 부터 $L$ 까지, 세로 좌표는 아래쪽에서부터 $1$ 부터 $W$ 까지 센다.

미로의 오두막은 모두 입구지만 출구는 하나뿐이다. 미로의 모양과 죄수가 있는 입구 오두막, 출구 오두막이 주어진다. 죄수가 출구 오두막까지 갈 수 있는지 판정하라.

입력

첫 줄에 테스트 케이스의 개수 $P$ 가 주어진다.

각 테스트 케이스의 첫 줄에는 자연수 여섯 개 $L$ , $W$ , $A$ , $B$ , $C$ , $D$ 가 공백으로 구분되어 주어진다.

$L$ 은 미로의 가로 길이, $W$ 는 미로의 세로 길이이다.
$A$ 와 $B$ 는 죄수가 있는 입구 오두막의 가로 좌표와 세로 좌표이다.
$C$ 와 $D$ 는 출구 오두막의 가로 좌표와 세로 좌표이다.

이어서 $W$ 개의 줄에 각각 문자 $L$ 개가 주어진다. 각 문자는 + 또는 *이다. 이 줄들은 미로의 위쪽부터 차례대로 주어지므로, $i$ 번째 줄은 세로 좌표가 $W+1-i$ 인 오두막을 나타낸다.

$1 \le P \le 20$ , $1 \le L \le 500$ , $1 \le W \le 500$ , $1 \le A, C \le L$ , $1 \le B, D \le W$ 이고, 모든 테스트 케이스의 $L \times W$ 합은 $250000$ 이하이다.

출력

각 교도소마다 죄수가 탈출할 수 있으면 YES, 그렇지 않으면 NO를 한 줄에 하나씩 출력한다.

예제2

예제 1

입력

2
4 2 1 2 4 1
++**
*+++
3 2 2 2 3 1
+*+
*+*

예상 출력

YES
NO

예제 2

입력

2
6 1 1 1 6 1
++++++
6 1 1 1 6 1
+++*++

예상 출력

YES
NO