Các nhà địa chất đôi khi chia một khu vực đất đai thành các vùng khác nhau dựa trên nơi nước mưa chảy xuống. Những vùng này được gọi là lưu vực thoát nước.

Cho một bản đồ độ cao (một mảng 2 chiều chứa các độ cao), hãy đánh nhãn bản đồ sao cho các vị trí trong cùng một lưu vực thoát nước có cùng một nhãn, tuân theo các quy tắc sau:

• Từ mỗi ô, nước chảy xuống tối đa một trong 4 ô lân cận của nó.
• Đối với mỗi ô, nếu không có ô nào trong 4 ô lân cận có độ cao thấp hơn ô hiện tại, thì nước không chảy, và ô hiện tại được gọi là một hố thu (sink).
• Ngược lại, nước sẽ chảy từ ô hiện tại đến ô lân cận có độ cao thấp nhất.
• Trong trường hợp có sự bằng nhau về độ cao thấp nhất, nước sẽ chọn hướng đầu tiên có độ cao thấp nhất từ danh sách này: Bắc, Tây, Đông, Nam.

Mọi ô chảy trực tiếp hoặc gián tiếp vào cùng một hố thu đều thuộc cùng một lưu vực thoát nước. Mỗi lưu vực được đánh nhãn bằng một chữ cái viết thường duy nhất, sao cho khi các hàng của bản đồ được nối lại từ trên xuống dưới, chuỗi kết quả là nhỏ nhất về mặt từ điển. (Cụ thể, lưu vực của ô Tây-Bắc ngoài cùng luôn được đánh nhãn là 'a'.)

Dữ liệu vào

Dòng đầu tiên của tệp đầu vào sẽ chứa số lượng bản đồ, \(T\). Tiếp theo là \(T\) bản đồ, mỗi bản đồ bắt đầu bằng hai số nguyên trên một dòng — \(H\) và \(W\) — chiều cao và chiều rộng của bản đồ, tính theo số ô. \(H\) dòng tiếp theo, mỗi dòng chứa một hàng của bản đồ, từ bắc xuống nam, mỗi hàng chứa \(W\) số nguyên, từ tây sang đông, xác định độ cao của các ô.

Dữ liệu ra

Đối với mỗi trường hợp kiểm thử, xuất ra \(1+H\) dòng. Dòng đầu tiên phải có dạng:

Case #X:

trong đó \(X\) là số thứ tự trường hợp kiểm thử, bắt đầu từ 1. \(H\) dòng tiếp theo phải liệt kê các nhãn lưu vực cho mỗi ô, theo cùng thứ tự như chúng xuất hiện trong đầu vào.

Ràng buộc

\(T \le 100\).

Phân nhóm

Tập dữ liệu nhỏ (Small dataset)

\(1 \le H, W \le 10\).
\(0 \le \text{altitudes} < 10\).
Sẽ có tối đa hai lưu vực.

Tập dữ liệu lớn (Large dataset)

\(1 \le H, W \le 100\).
\(0 \le \text{altitudes} < 10,000\).
Sẽ có tối đa 26 lưu vực.

Đ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
3 3
9 6 3
5 9 6
3 5 9
1 10
0 1 2 3 4 5 6 7 8 7
2 3
7 6 7
7 6 7
5 5
1 2 3 4 5
2 9 3 9 6
3 3 0 8 7
4 9 8 9 8
5 6 7 8 9

Case #1:
a b b
a a b
a a a
Case #2:
a a a a a a a a a b
Case #3:
a a a
b b b
Case #4:
a a a a a
a a b b a
a b b b a
a b b b a
a a a a a

Nguồn

Google Code Jam 2009, Vòng loại, bài Watersheds.

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