Hang động đang bốc cháy và khói ở khắp mọi nơi! Bạn đang cố gắng đào đường xuống đáy hang, nơi bạn có thể hít thở. Vấn đề là có một số lỗ hổng không khí bên trong hang, và bạn không muốn bị rơi quá nhiều nếu không bạn sẽ bị thương.

Hang động được biểu diễn dưới dạng một ma trận \(R \times C\) với các lỗ hổng không khí và các ô đá cứng. Bạn bắt đầu tại vị trí \((1, 1)\), nằm ở góc trên bên trái.

Bạn có thể di chuyển từng ô một, sang trái hoặc sang phải, nếu ô đó trống (là một lỗ hổng không khí). Sau khi di chuyển, nếu ô bên dưới trống, bạn sẽ rơi xuống cho đến khi chạm vào đá cứng hoặc đáy hang. Khoảng cách rơi phải tối đa là \(F\), nếu không bạn sẽ bị thương. Bạn phải xuống được đáy hang mà không bị thương. Trong khi đang rơi, bạn không thể di chuyển sang trái hoặc sang phải.

Bạn cũng có thể "đào", biến một ô chứa đá cứng thành một lỗ hổng không khí. Ô mà bạn đào có thể là một trong hai ô: ô bên phải và bên dưới bạn, hoặc ô bên trái và bên dưới bạn. Ô phía trên ô bạn đang đào phải là ô trống. Trong khi đang rơi, bạn không thể đào.

Mục tiêu của bạn không chỉ là xuống được đáy hang, mà còn phải "đào" ít ô nhất có thể.

Hãy mô tả các thao tác bằng một ví dụ cụ thể:

Bạn bắt đầu tại \((1, 1)\) và di chuyển sang phải 3 lần đến vị trí \((1, 4)\), giống như trong hình.
Bạn đào đá tại vị trí \((2, 5)\). Ô "A" trở nên trống.
Bạn di chuyển sang phải một vị trí và vì không có ô bên dưới, bạn rơi 3 ô xuống vị trí \((4, 5)\).
Bạn đào đá tại vị trí \((5, 6)\). Ô "B" trở nên trống.
Bạn di chuyển sang phải một vị trí và vì không có ô bên dưới, bạn rơi 1 ô xuống vị trí \((5, 6)\).
Bạn đã xuống được đáy hang bằng cách đào 2 ô.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(N\). \(N\) bộ test tiếp theo.
Dòng đầu tiên của mỗi bộ test có định dạng:

R C F

trong đó \(R\) là số hàng trong hang động, \(C\) là số cột trong hang động, và \(F\) là khoảng cách tối đa bạn có thể rơi mà không bị thương.
Tiếp theo là \(R\) hàng, mỗi hàng chứa \(C\) ký tự. Mỗi ký tự có thể là một trong hai loại:

• # cho đá cứng
• . cho lỗ hổng không khí

Ô trên cùng bên trái luôn trống, và ô bên dưới nó sẽ là đá cứng.

Dữ liệu ra

Với mỗi bộ test, hãy in ra một dòng có định dạng:

Case #X: No/Yes [D]

trong đó \(X\) là số thứ tự bộ test, bắt đầu từ 1. In ra "No" nếu bạn không thể xuống được đáy hang. In ra "Yes \(D\)" nếu có thể xuống được đáy hang và số lượng ô tối thiểu cần đào là \(D\).

Ràng buộc

• \(1 \le N \le 50\)
• \(1 \le F < R\)

Phân nhóm

• Small dataset: \(2 \le R \le 10, 2 \le C \le 6\).
• Large dataset: \(2 \le R \le 50, 2 \le C \le 50\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
2 2 1
.#
##
3 3 1
...
###
###
3 2 1
..
#.
..

Case #1: No
Case #2: Yes 3
Case #3: No

Nguồn

Google Code Jam 2009, Vòng 2, bài A Digging Problem.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.