Bạn đang ở trên vách núi Everest. Bạn cần tìm nơi trú ẩn trước khi bị đóng băng, và trời thì tối om! Bạn phải làm gì đây?

Tin tốt là bạn đã ghi nhớ sơ đồ của ngọn núi. Nó là một lưới với một số ô không thể đi qua và các ô khác chứa các hang động nơi bạn có thể nghỉ ngơi qua đêm. Tin xấu là bạn không biết mình đang ở đâu, và vách núi quá dốc để leo lên. Tất cả những gì bạn có thể làm là di chuyển sang trái, sang phải hoặc xuống dưới.

Dưới đây là một ví dụ về sơ đồ, với . đại diện cho một ô có thể đi qua, # đại diện cho một ô không thể đi qua, và các con số đại diện cho các hang động.

######
##...#
#..#.#
#...##
#0#..#
####1#
######

Vì trời rất tối, bạn sẽ di chuyển bằng cách tuân theo một kế hoạch, đó là một chuỗi các chỉ dẫn, mỗi chỉ dẫn yêu cầu bạn di chuyển một ô sang trái, sang phải hoặc xuống dưới. Nếu một chỉ dẫn đưa bạn đến một ô có thể đi qua hoặc một hang động, bạn sẽ thực hiện nó. Nếu nó đưa bạn đến một ô không thể đi qua, bạn sẽ phải bỏ qua nó. Dù thế nào đi nữa, bạn vẫn sẽ tiếp tục bước tiếp theo, và cứ thế, cho đến khi bạn thực hiện hết toàn bộ kế hoạch.

Để hỗ trợ việc đi xuống, bạn muốn tìm ra hai điều cho mỗi hang động C:

• Những ô nào có thể đi tới được C? Chúng ta sẽ ký hiệu tập hợp các ô này là \(S_C\), và số lượng của chúng là \(n_C\).
• Có tồn tại một kế hoạch duy nhất mà nếu thực hiện từ bất kỳ ô nào trong \(S_C\), bạn sẽ kết thúc tại hang động C không? Nếu có, chúng ta nói hang động đó là may mắn (lucky).

Lưu ý rằng bạn có thể đi ngang qua nhiều hang động trong khi thực hiện một kế hoạch. Điều quan trọng duy nhất là ô bạn kết thúc sau khi thực hiện tất cả các bước, chứ không phải các hang động bạn ghé thăm dọc đường.

Ví dụ, trong sơ đồ trên, hang động 0 là may mắn. Có 9 ô mà từ đó có thể đến được nó (bao gồm cả chính nó), và kế hoạch "sang trái-sang trái-xuống-xuống-sang trái-xuống" sẽ giúp bạn kết thúc tại hang động từ bất kỳ ô nào trong số đó.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, T. T bộ thử nghiệm tiếp theo, bắt đầu bằng một dòng chứa các số nguyên R và C, đại diện cho số hàng và số cột của sơ đồ ngọn núi.

Tiếp theo là R dòng, mỗi dòng chứa C ký tự, mô tả sơ đồ ngọn núi. Như trong ví dụ trên, ký tự # đại diện cho ô không thể đi qua, ký tự . đại diện cho ô có thể đi qua, và các chữ số '0'-'9' đại diện cho các hang động (cũng là các ô có thể đi qua).

Dữ liệu ra

Với mỗi bộ thử nghiệm, trước tiên hãy in ra một dòng chứa "Case #x:", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1). Đối với mỗi hang động C, bắt đầu từ 0 và đếm ngược lên, hãy viết một dòng "C: \(n_C\) \(L_C\)". Ở đây, C là số hiệu hang động, \(n_C\) là số lượng ô bạn có thể đi tới hang động đó, và \(L_C\) là chuỗi "Lucky" hoặc "Unlucky", như đã định nghĩa ở trên.

Ràng buộc

• Sẽ có từ 1 đến 10 hang động (bao gồm cả 1 và 10).
• Nếu có d hang động, chúng sẽ được gắn nhãn bằng các chữ số {0, 1, ..., d - 1}, và không có hai hang động nào có cùng nhãn.
• Tất cả các ô trên biên của sơ đồ ngọn núi đều không thể đi qua.
• 1 ≤ T ≤ 20.

Phân nhóm

• Test set 1 (Visible): 3 ≤ R, C ≤ 10.
• Test set 2 (Hidden): 3 ≤ R, C ≤ 60.

Đ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
7 5
#####
##0##
##1.#
##2##
#3..#
#.#.#
#####
7 6
######
##...#
#..#.#
#...##
#0#..#
####1#
######

Case #1:
0: 1 Lucky
1: 3 Lucky
2: 4 Unlucky
3: 7 Lucky
Case #2:
0: 9 Lucky
1: 11 Unlucky

Nguồn

Google Code Jam 2012, Vòng 2, bài Descending in the Dark.

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