Mưa xói mòn đảo Atlantis cho tới khi đất biến mất. Bản đồ là lưới \(H\times W\), mỗi ô có độ cao đất không âm (mét) so với mực biển. Ngoài bản đồ có độ cao 0; ô cao 0 là nước, ô cao hơn là đất.

Nước chảy từ ô nguồn sang ô chung cạnh nếu mực nước ở đích không cao hơn nguồn. Mưa rất nhanh: nếu chưa có lối chảy, nước tích lại tới khi có. Ngoài bản đồ nhận vô hạn nước. Với bản đồ:

5 9 9 9 9 9
0 8 9 0 2 5
3 9 9 9 9 9

gọi mực nước là độ cao đất cộng độ sâu nước, trạng thái nhanh chóng thành:

5 9 9 9 9 9
0 8 9 5 5 5
3 9 9 9 9 9

Ô 0 ở giữa không nối ra ngoài nên chứa nước; ô 0 ở biên nối được ra ngoài. Nếu có nhiều đích chảy, nước chọn ô có mực thấp nhất (hòa không ảnh hưởng).

Mỗi cuối ngày, nếu nước chảy từ \(S\) sang \(T\), đất ở \(S\) giảm \(\min(\text{WaterLevel}(S)-\text{WaterLevel}(T),M)\). Mọi ô xói mòn đồng thời. Với \(M=5\), bản đồ thành:

0 4 4 4 4 4
0 3 5 0 2 0
0 4 4 4 4 4

Nước dư chảy đi và nước lại tích, cho mực:

0 4 4 4 4 4
0 3 5 2 2 0
0 4 4 4 4 4

Sau ngày tiếp theo:

0 0 0 0 0 0
0 0 2 0 0 0
0 0 0 0 0 0

Hãy tính số ngày tới khi mọi độ cao bằng 0.

Dữ liệu vào

Dòng đầu là \(T\). Mỗi test bắt đầu bằng \(H,W,M\), sau đó \(H\) dòng, mỗi dòng \(W\) độ cao.

Dữ liệu ra

In Case #x: y, với \(y\) là số ngày đảo bị xói mòn hoàn toàn.

Ràng buộc

• \(1\le T\le40\); bộ nhớ 1 GB.

Phân nhóm

• Nhỏ: \(1\le H,W\le10\), \(1\le M\le100\), độ cao 0–100.
• Lớn: \(1\le H,W\le20\), \(1\le M\le10^{15}\), độ cao 0–\(10^{15}\).

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

2
3 6 5
5 9 9 9 9 9
0 8 9 0 2 5
3 9 9 9 9 9
3 6 3
3 8 10 11 10 8
7 5 2 12 8 8
6 9 11 9 8 4

Case #1: 3
Case #2: 5

3 8 10 11 10 8
7 7 7 12 8 8
6 9 11 9 8 4

0 5 7 8 7 5
4 5 2 9 8 5
3 6 8 6 5 1

0 2 4 5 4 2
1 4 2 6 5 2
0 3 5 3 2 0

0 0 1 2 1 0
0 1 2 3 2 0
0 0 2 0 0 0

0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0

Nguồn

Google Code Jam 2011, Chung kết thế giới, bài Rains Over Atlantis.

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