Cuộc chiến giải phóng thành phố khỏi những kẻ xâm lược ngoài hành tinh đã kết thúc! Mọi người vui mừng vì tình yêu và hòa bình đã trở lại.

Thành phố được biểu diễn bằng lưới \(R\) hàng, \(C\) cột. Một số ô là tòa nhà — không ai có thể nhìn, bắn hay đi xuyên qua — và một số ô là đường phố — mọi người có thể nhìn, bắn và đi qua. Trong chiến tranh, những kẻ xâm lược nay đã bị đánh bại đặt các tháp pháo an ninh tự động trên đường phố, không phải trong tòa nhà. Các tháp gây nguy hiểm cho dân thường, nhưng may mắn là cũng có một số binh sĩ trên đường phố. Ban đầu không binh sĩ nào đứng cùng ô với tháp.

Tháp pháo không di chuyển. Chúng nhỏ nên không chặn tầm nhìn và đường đạn. Binh sĩ không thể đi xuyên qua ô của một tháp còn hoạt động, nhưng có thể đi qua sau khi tháp bị phá. Tháp chỉ nhìn thấy binh sĩ trong các ô có đường ngắm ngang hoặc dọc. Nếu binh sĩ đi vào một ô như vậy, tháp chưa bắn; nếu cô ấy cố rời khỏi ô đó, dù vừa đi vào hay bắt đầu tại đó, tháp sẽ bắn. May mắn thay, binh sĩ vẫn có thể bắn khi đứng yên trong ô và tháp không coi đó là chuyển động. Vì thế không binh sĩ nào thật sự phải chết: trong trường hợp xấu nhất họ có thể đứng im chờ cứu viện, có lẽ rất lâu.

Mỗi binh sĩ có thể thực hiện tổng cộng \(M\) bước đơn vị; mỗi bước sang một ô kề ngang hoặc dọc. Binh sĩ có thể đi xuyên qua nhau và không chặn tầm nhìn của binh sĩ hay tháp. Mỗi binh sĩ có một viên đạn. Nếu có một tháp trong đường ngắm ngang hoặc dọc, cô ấy có thể bắn phá nó. Mỗi phát chỉ phá một tháp, nhưng các binh sĩ bắn giỏi đến mức có thể bắn xuyên qua một hoặc nhiều tháp hay binh sĩ trên cùng đường ngắm để trúng một tháp xa hơn.

Bạn được cho bản đồ có đánh dấu vị trí binh sĩ và tháp. Số tháp lớn nhất họ có thể phá là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng ba số nguyên \(C\) (chiều rộng bản đồ), \(R\) (chiều cao) và \(M\) (số bước đơn vị mỗi binh sĩ có thể đi). Tiếp theo là \(R\) dòng, mỗi dòng \(C\) ký tự: . là đường phố, # là tòa nhà, S là binh sĩ và T là tháp pháo.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số tháp lớn nhất có thể phá. Sau đó in \(y\) dòng; dòng thứ \(i\) chứa hai số nguyên \(s_i,t_i\), biểu thị hành động thứ \(i\) là binh sĩ \(s_i\) phá tháp \(t_i\). Không cần chỉ rõ đường đi. Nếu có nhiều chiến lược hợp lệ, có thể in bất kỳ chiến lược nào.

Binh sĩ được đánh số từ 1 theo thứ tự đọc: trái sang phải trên hàng đầu, rồi trái sang phải trên hàng kế tiếp, từ trên xuống dưới. Tháp có hệ đánh số độc lập, cũng bắt đầu từ 1 và theo cùng thứ tự.

Ràng buộc

• \(1\le T\le100\).
• \(0\le M<C\times R\).

Phân nhóm

Test Set 1 (Visible): \(1\le C,R\le30\); số ký hiệu S từ 1 đến 10 và số ký hiệu T từ 1 đến 10.

Test Set 2 (Hidden): \(1\le C,R\le100\); số ký hiệu S từ 1 đến 100 và số ký hiệu T từ 1 đến 100.

Đ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ụ

4
2 2 1
#S
T.
2 6 4
.T
.T
.T
S#
S#
S#
5 5 4
.....
SS#.T
SS#TT
SS#.T
.....
3 3 8
S.#
.#.
#.T

Case #1: 1
1 1
Case #2: 3
3 3
1 1
2 2
Case #3: 3
1 2
2 1
6 3
Case #4: 0

Nguồn

Google Code Jam 2017, Vòng 2, bài Shoot the Turrets.

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