Marlin là một chú cá bị lạc mất con trai và đang cố tìm con. May mắn thay, khi đang bơi cùng hai anh em Wally và Seymour, rùa Cynthia gặp Marlin. Cynthia biết chính xác Marlin cần đi đâu và có thể chỉ đường rất tỉ mỉ. Marlin thông minh, có thể làm theo hoàn hảo, nhưng ghi nhớ một danh sách chỉ dẫn dài lại khó. Cynthia cần làm danh sách đó thật ngắn.

Marlin sống trong một ma trận \(R\) hàng và \(C\) cột. Một số ô nguy hiểm, không thể đi vào. Marlin và con trai hiện ở hai ô an toàn khác nhau; con trai Marlin không bao giờ chuyển ô.

Cynthia đưa chỉ dẫn dưới dạng một chương trình gồm danh sách lệnh, mỗi dòng là một trong năm loại:

• N: đi một ô về bắc (lên);
• S: đi một ô về nam (xuống);
• W: đi một ô về tây (trái);
• E: đi một ô về đông (phải);
• G(i): nhảy tới dòng lệnh thứ \(i\) (đánh số từ 1).

Sau khi thực hiện một trong bốn lệnh di chuyển, Marlin chuyển sang dòng kế tiếp nếu có. Nếu không còn dòng kế tiếp, Marlin chỉ đứng yên mãi mãi.

Ví dụ, với chương trình

1: N
2: E
3: G(6)
4: S
5: G(1)
6: W
7: G(4)

Marlin đi bắc (dòng 1), rồi đông (2), nhảy tới dòng 6 mà không di chuyển (3), đi tây (6), nhảy tới dòng 4 (7), đi nam (4), nhảy tới dòng 1 (5), rồi đi bắc (1), v.v.

Nếu ở bất kỳ thời điểm nào Marlin và con trai cùng ở một ô, họ sẽ đoàn tụ và Marlin ngừng làm theo mọi lệnh. Hãy tìm số dòng nhỏ nhất trong một chương trình đưa Marlin tới cùng ô với con trai mà không bao giờ vào ô nguy hiểm hay đi ra ngoài biên ma trận. Mọi lệnh G phải nhảy tới một dòng tồn tại trong chương trình.

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 \(R,C\), số hàng và cột. Tiếp theo là \(R\) dòng, mỗi dòng là một chuỗi \(C\) ký tự. Ký tự \(A_{ij}\) ở hàng \(i\), cột \(j\) là # nếu ô nguy hiểm, M nếu đó là vị trí hiện tại của Marlin, N nếu đó là vị trí hiện tại của con trai Marlin, và . nếu là ô an toàn đang trống.

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), còn y là IMPOSSIBLE nếu không có chương trình thỏa điều kiện, hoặc là số lệnh nhỏ nhất của một chương trình như vậy.

Ràng buộc

• \(1\le T\le100\).
• \(A_{ij}\) là một trong #, ., M, N.
• Có đúng một cặp \((i,j)\) sao cho \(A_{ij}={}\)M và đúng một cặp sao cho \(A_{ij}={}\)N.

Phân nhóm

Test Set 1 (Visible): \(1\le R\le10\), \(1\le C\le10\).

Test Set 2 (Hidden): Với nhiều nhất 10 bộ test, \(1\le R,C\le100\); với các bộ test còn lại, \(1\le R,C\le50\).

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

5
2 5
N...#
....M
2 5
N#...
...#M
5 5
N..##
#.###
#...#
##.##
##..M
5 5
..N##
#.###
#...#
##.##
##..M
3 3
#M#
###
#N#

Case #1: 4
Case #2: 7
Case #3: 5
Case #4: 6
Case #5: IMPOSSIBLE

1: W
2: N
3: S
4: G(1)

1: W
2: N
3: W
4: G(3)

1: N
2: W
3: W
4: S
5: W
6: W
7: N

1: W
2: W
3: N
4: N
5: G(2)

1: W
2: W
3: N
4: N
5: E
6: G(1)

Nguồn

Google Code Jam 2019, Chung kết thế giới, bài Go To Considered Helpful.

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