#1147 Portal

1 s   128 MB  

Description

LIBe로부터 Ajou Programming Contest의 문제를 내달라는 부탁을 받은 Toivoa는 어떤 문제를 내야할지 고민하던 중 Valve의 게임 Portal™을 플레이하게 되었다.
 
 
Portal™에서 게임 내에 있는 기계 장치들을 통해서 게임 내의 공간에 빨강색 포탈이 열리며, 플레이어는 파란색 포탈을 열 수 있는 총을 가지고 있다.
 
 
이 총을 통해 플레이어는 벽이나 바닥 등 원하는 위치에 파란색 포탈을 열고 게임 내의 공간에 열려있는 빨강색 포탈로 이동할 수 있으며, 빨강색 포탈을 통해서 다시 파란색 포탈로 돌아오는 것도 가능하다.
플레이어가 다른 위치에 파란색 포탈을 열기 전까지 기존에 열려있던 파란색 포탈은 닫히지 않으며, 플레이어가 다른 위치에 파란색 포탈을 여는 순간 기존의 파란색 포탈은 닫히게 된다.
 
 
시간이 지남에 따라서 게임 내의 기계 장치들이 작동해서 빨강색 포탈의 위치가 변하는데, 게임을 플레이하던 Toivoa는 빨강색 포탈이 열리는 위치가 항상 순환해서 나타난다는 사실을 발견하였다. 예를 들어 빨강색 포탈이 열리는 위치가 3 군데 있다고 하면 1번 위치, 2번 위치, 3번 위치, 1, 2, 3, ... 의 순서로 번갈아가면서 계속 열리게 된다.
 
 
게임을 클리어하기 위해서 플레이어는 게임 내에 있는 상자를 찾은 다음, 이 상자를 이용해서 문을 여는 스위치를 동작시킨 후 문을 통해 밖으로 나가야 한다.
 
Toivoa는 이 게임에서 힌트를 얻어서, 게임의 상태가 주어졌을 때, 플레이어가 이 게임을 클리어할 수 있는지 알아내는 문제를 내기로 하였다.
 
문제를 간단히 하기 위해 빨강색 포탈의 위치는 1초마다 바뀌며, 빨강색 포탈이 열리는 위치는 최대 9 곳으로 제한한다. 
 
 
또한 플레이어가 한 칸 움직이는데 걸리는 시간 또한 1초이며, 대각선으로 이동하는것은 불가능하다고 하자. 물론 플레이어가 이동하지 않고 가만히 서있을 수도 있다.
 
또한 포탈을 만드는 총을 쏘거나 상자를 드는 등의 이동이 아닌 행동에 걸리는 시간은 없는 것으로 한다. 
 
예를 들어 플레이어가 게임이 시작하자마자 발밑에 포탈을 만들어서 이동하는 경우 게임이 시작하는 시점에 열려있는 1번 포탈로 이동한다.
 
 
당신은 주어진 게임 공간에서 플레이어가 게임을 클리어할 수 있는지 출력하는 프로그램을 작성해야 한다.
 

 

Input

입력의 첫줄에는 테스트 케이스의 개수 T (T ≤ 20)가 주어진다.
각각의 테스트 케이스의 첫 줄에는 공간의 크기 N, M (3 ≤ N, M ≤ 20) 이 주어진다.
 
이후 N줄에 걸쳐서 공간의 정보가 주어진다. #은 벽을 의미하며 .은 플레이어가 이동할 수 있는 위치이다.
 
또한 P는 플레이어, B는 박스, S는 스위치, D는 문이며, 숫자는 빨강색 포탈이 열리는 위치와 순서를 의미한다.
 
입력된 공간의 외곽은 모두 벽으로 둘러싸여 있으며, 플레이어는 박스나 스위치, 문을 넘어서 이동할 수있다.
 

 

Output

각각의 테스트 케이스에 대해서 플레이어가 게임을 클리어할 수 있는지 여부를 YES / NO로 출력한다.

 

Sample Input

Sample Output

2
10 10
.......#..
#####..#..
#P..#..#.3
##.##S.###
.#1#..6#.#
.#######.#
.####...D#
.#B.#.5###
##..#..#..
...2#..#4.
5 5
##P#.
S#B#1
3###.
#####
D..#2
YES
NO

Source

2010 Ajou University Programming Contest