Ben, một nhà thiết kế trò chơi điện tử tài ba, đang thiết kế các bản đồ cho trò chơi di động thực tế tăng cường sắp ra mắt. Gần đây anh tạo một bản đồ biểu diễn bằng ma trận \(R\) hàng và \(C\) cột. Bản đồ gồm các ký tự . biểu thị ô trống, các ký tự # biểu thị tường không thể đi qua, đúng một vị trí bắt đầu S và đúng một vị trí kết thúc F. Ví dụ, bản đồ có thể như sau:

#############
#S..#..##...#
###.##..#.#F#
#...##.##.###
#.#.........#
#############

Trong trò chơi của Ben, một đường đi là một dãy bước (lên, xuống, trái hoặc phải) để đi từ ô này sang ô khác mà không đi xuyên qua tường.

Ben coi một bản đồ là tốt nếu có các tính chất sau:

• Có đường đi giữa mọi cặp ô trống (bao gồm vị trí bắt đầu và kết thúc).
• Để bảo toàn độ vững của cấu trúc, các tường phải tiếp xúc bằng cạnh chứ không chỉ bằng góc. Trong mọi vùng \(2\times2\) của bản đồ, nếu vùng chứa đúng hai ô tường thì hai tường đó phải cùng hàng hoặc cùng cột. Nói cách khác, không có vùng \(2\times2\) nào có tường theo một trong hai cấu hình:

#.   .#
.#   #.

• Biên bản đồ chỉ gồm tường không thể đi qua. Một ô thuộc biên nếu nó nằm ở hàng trên cùng/dưới cùng hoặc cột trái cùng/phải cùng.

Độ dài đường đi ngắn nhất là số bước ít nhất cần để đi từ vị trí bắt đầu đến vị trí kết thúc. Chẳng hạn, đường đi ngắn nhất trong ví dụ trên dài 17 bước.

Là một người làm bản đồ thông minh, Ben nhận ra bản đồ của mình quá khó đối với bạn bè. Anh muốn giảm độ khó bằng cách dỡ bỏ một số tường. Cụ thể, anh muốn biết có thể dỡ bỏ không hoặc nhiều tường sao cho đường đi ngắn nhất từ đầu đến cuối dài đúng \(D\) bước và bản đồ thu được vẫn tốt hay không. Chỉ tìm được một đường đi dài \(D\) là chưa đủ; \(D\) phải là số bước của đường đi ngắn nhất.

Ví dụ, nếu \(D=15\), ta có thể dỡ bức tường ngay bên dưới vị trí kết thúc để có một lời giải tốt:

#############
#S..#..##...#
###.##..#.#F#
#...##.##.#.#
#.#.........#
#############

Không có lời giải nếu \(D=5\).

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng một dòng chứa ba số nguyên cách nhau bởi dấu cách \(R,C,D\): số hàng, số cột của bản đồ và số bước mong muốn của đường đi ngắn nhất sau khi có thể dỡ tường. Tiếp theo là \(R\) dòng, mỗi dòng gồm \(C\) ký tự thuộc . , #, S, F, biểu diễn bản đồ của Ben.

Bản đồ được bảo đảm là tốt theo định nghĩa trong đề.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là POSSIBLE hoặc IMPOSSIBLE tùy theo có thể làm đường đi ngắn nhất bằng \(D\) bằng cách dỡ một số tường mà bản đồ vẫn tốt hay không. Nếu có thể, in thêm \(R\) dòng, mỗi dòng \(C\) ký tự, biểu diễn bản đồ mới. Trong đầu ra, thay các ký tự # của những tường đã dỡ (nếu có) bằng ..

Nếu có nhiều lời giải, bạn có thể in bất kỳ lời giải nào.

Ràng buộc

• \(1\le T\le100\).
• Mỗi bộ test chứa đúng một S và đúng một F.
• Tệp đầu vào có kích thước không quá 3 MB.

Phân nhóm

• Test Set 1 (Hiển thị): \(3\le R\le40\), \(3\le C\le40\), \(1\le D\le1600\).
• Test Set 2 (Ẩn): \(3\le R\le1000\), \(3\le C\le1000\), \(1\le D\le10^6\).

Đ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
6 13 15
#############
#S..#..##...#
###.##..#.#F#
#...##.##.###
#.#.........#
#############
5 8 3
########
#S.....#
####...#
#F.....#
########
4 10 11
##########
#S#...#.F#
#...#...##
##########

Case #1: POSSIBLE
#############
#S..#..##...#
###.##..#.#F#
#...##.##.#.#
#.#.........#
#############
Case #2: IMPOSSIBLE
Case #3: POSSIBLE
##########
#S#...#.F#
#...#...##
##########

Nguồn

Google Code Jam 2016, Chung kết thế giới, bài Map Reduce.

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