A 굴착 문제

동굴에 불이 났고 사방이 연기로 가득하다! 당신은 숨을 쉴 수 있는 동굴 바닥까지 길을 파 내려가려고 한다. 문제는 동굴 안에 공기 구멍이 몇 군데 있으며, 너무 많이 떨어지면 다치므로 이를 피해야 한다는 것이다.

동굴은 공기 구멍과 단단한 암석 칸으로 이루어진 R x C 행렬로 표현된다. 왼쪽 위 모서리에 있는 위치 (1, 1)에서 시작한다. 왼쪽이나 오른쪽의 칸이 비어 있다면(공기 구멍이라면) 한 번에 한 칸씩 그 방향으로 이동할 수 있다. 이동한 뒤 아래 칸이 비어 있다면, 단단한 암석이나 동굴 바닥에 닿을 때까지 아래로 떨어진다. 낙하 거리는 최대 F여야 하며, 그렇지 않으면 다친다. 다치지 않고 동굴 바닥에 도달해야 한다. 떨어지는 동안에는 왼쪽이나 오른쪽으로 이동할 수 없다.

또한 "dig"하여 단단한 암석이 있는 칸을 공기 구멍으로 바꿀 수 있다. 팔 수 있는 칸은 두 칸 중 하나로, 오른쪽 아래 칸 또는 왼쪽 아래 칸이다. 파려는 칸의 위쪽 칸은 비어 있어야 한다. 떨어지는 동안에는 팔 수 없다.

목표는 동굴 바닥에 도달하는 것뿐만 아니라, 가능한 한 적은 칸을 "dig"하는 것이다.

구체적인 예제로 연산을 설명하자:

위치 (1, 1)에서 시작하여 그림과 같이 오른쪽으로 3번 이동해 위치 (1, 4)에 도달한다. 위치 (2, 5)의 암석을 판다. 칸 "A"이 비게 된다. 오른쪽으로 한 칸 이동하면 아래에 칸이 없으므로 3칸 떨어져 위치 (4, 5)에 도달한다. 위치 (5, 6)의 암석을 판다. 칸 "B"이 비게 된다. 오른쪽으로 한 칸 이동하면 아래에 칸이 없으므로 1칸 떨어져 위치 (5, 6)에 도달한다. 2개의 칸을 파서 동굴 바닥에 도달했다.

제한

메모리 제한: 1 GB. 1 ≤ N ≤ 50 1 ≤ F < R

작은 데이터 세트

시간 제한: 40초. 2 ≤ R ≤ 10 2 ≤ C ≤ 6

큰 데이터 세트

시간 제한: 60초. 2 ≤ R ≤ 50 2 ≤ C ≤ 50

입력의 첫 번째 줄에는 케이스 수 N이 주어진다. 이어서 N개의 테스트 케이스가 주어진다. 각 케이스의 첫 번째 줄은 다음 형식이다.

R C F

여기서 R은 동굴의 행 수, C는 동굴의 열 수이며, F는 다치지 않고 떨어질 수 있는 최대 거리이다. 이어서 각각 C개의 문자를 포함하는 R개의 행이 주어진다. 각 문자는 다음 두 가지 중 하나이다.

• #은 단단한 암석이다

• .은 공기 구멍이다

왼쪽 위 칸은 항상 비어 있고 그 아래 칸은 단단한 암석이다.

각 테스트 케이스마다 다음 형식으로 한 줄을 출력한다.

Case #X: No/Yes [D]

여기서 X는 1부터 시작하는 케이스 번호이다. 동굴 바닥에 도달할 수 없다면 "No"을 출력한다. 동굴 바닥에 도달할 수 있고 파야 하는 칸의 최소 개수가 D라면 "Yes D"을 출력한다.