cho.sh

동굴 파기 (큰 입력)

아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

동굴에 불이 나서 연기가 가득하다. 숨을 쉴 수 있는 동굴 바닥까지 굴을 파고 내려가려 한다. 문제는 동굴 안에 빈 공간이 있다는 점이다. 너무 많이 떨어지면 다친다.

동굴은 R×CR \times C 격자다. 각 칸은 단단한 바위이거나 빈 공간이다. 처음에는 왼쪽 위 칸인 (1,1)(1, 1)에 서 있다. (r,c)(r, c)는 위에서 rr번째 행, 왼쪽에서 cc번째 열의 칸을 뜻한다.

한 번에 한 칸씩 왼쪽이나 오른쪽으로 움직일 수 있고, 옮겨 갈 칸이 빈 공간일 때만 움직인다. 움직인 뒤 바로 아래 칸이 비어 있으면 단단한 바위에 닿거나 동굴 바닥에 닿을 때까지 아래로 떨어진다. 떨어진 거리가 FF보다 크면 다치므로, 한 번에 떨어지는 거리는 항상 FF 이하여야 한다. 떨어지는 동안에는 좌우로 움직일 수 없다.

바위 칸을 파서 빈 공간으로 바꿀 수도 있다. (r,c)(r, c)에 서 있을 때 팔 수 있는 칸은 오른쪽 아래 (r+1,c+1)(r+1, c+1)과 왼쪽 아래 (r+1,c−1)(r+1, c-1) 두 가지뿐이다. 파려는 칸의 바로 위 칸, 즉 (r,c+1)(r, c+1)이나 (r,c−1)(r, c-1)이 빈 공간이어야 한다. 떨어지는 동안에는 팔 수 없다. 한자리에 선 채로 조건을 만족하는 칸을 여러 번 팔 수 있고, 한 번 판 칸은 그 뒤로도 계속 빈 공간이다.

목표는 다치지 않고 동굴 바닥인 RR번째 행의 칸에 도달하면서, 파는 칸의 수를 최소로 하는 것이다.

R=5R = 5, C=8C = 8, F=3F = 3인 아래 동굴로 동작을 설명한다.

  1. (1,1)(1, 1)에서 시작해 오른쪽으로 세 번 움직여 (1,4)(1, 4)로 간다.
  2. (2,5)(2, 5)의 바위를 판다. 그림의 A 칸이 빈 공간이 된다.
  3. 오른쪽으로 한 칸 움직이면 아래가 비어 있으므로 세 칸 떨어져 (4,5)(4, 5)에 선다.
  4. (5,6)(5, 6)의 바위를 판다. 그림의 B 칸이 빈 공간이 된다.
  5. 오른쪽으로 한 칸 움직이면 아래가 비어 있으므로 한 칸 떨어져 (5,6)(5, 6)에 선다.

두 칸을 파서 동굴 바닥에 도달했다.

입력

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

각 테스트 케이스의 첫 줄에는 세 정수가 주어진다.

R C F

RR은 동굴의 행 수, CC는 동굴의 열 수, FF는 다치지 않고 떨어질 수 있는 최대 거리다. 다음 RR개 줄에는 각각 공백 없이 CC개의 문자가 주어지고, 각 문자는 둘 중 하나다.

  • #는 단단한 바위
  • .는 빈 공간

왼쪽 위 칸은 항상 빈 공간이고, 그 바로 아래 칸은 항상 단단한 바위다.

제한

  • 1≤N≤501 \le N \le 50
  • 2≤R≤502 \le R \le 50
  • 2≤C≤502 \le C \le 50
  • 1≤F<R1 \le F < R

출력

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

Case #X: No

또는

Case #X: Yes D

XX는 1부터 시작하는 테스트 케이스 번호다. 동굴 바닥에 도달할 수 없으면 No를 출력한다. 도달할 수 있으면 Yes와 한 칸 띄고 최소로 파야 하는 칸의 수 DD를 출력한다.