27796번 - Go To Considered Helpful 서브태스크다국어채점 준비 중

문제

Marlin is a fish who lost his son and is trying to find him. Fortunately, he ran into Cynthia, a turtle, as she swam around with her brothers, Wally and Seymour. Cynthia knows exactly where Marlin needs to go, and she can be very precise in giving directions. While Marlin is smart and can follow them perfectly, keeping track of a long list of directions can be problematic. Cynthia needs to find a way to make the list of directions short.

Marlin lives in a matrix of R rows and C columns. Some cells of the matrix are dangerous and cannot be entered. Marlin and his son are currently in different non-dangerous cells. Marlin's son never moves to a different cell. Cynthia decided to give Marlin directions in the form of a program consisting of a list of instructions, each on a single line. Each instruction is of one of 5 types:

• N: move one cell North (up),
• S: move one cell South (down),
• W: move one cell West (left),
• E: move one cell East (right), and
• G(i): jump to the i-th line of the instruction list (counting starting from 1).

After executing a line with any of the first 4 instructions, Marlin jumps to the next line on the list if there is one. If there is no next line, Marlin just stands still forever.

For example, if Marlin were following the program

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

he would move North (line 1), then East (2), then jump to line 6 without physically moving (3), then move West (6), then jump to line 4 (7), then move South (4), then jump to line 1 (5), then move North (1), etc.

If at any point Marlin and his son are at the same cell, they will be reunited and Marlin will no longer follow any instructions. Cynthia the turtle wants to find out the smallest number of lines in a program that would get Marlin to the same cell as his son, without him ever going into a dangerous cell or moving outside of the matrix boundaries. All G instructions must jump to existing lines in the program.

입력

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing R and C, the number of rows and columns in the matrix. Then, R lines follow containing a string of C characters each. The j-th character of the i-th of these lines A_ij represents the cell in the i-th row and j-th column of the matrix. The character is # if the cell is dangerous, an uppercase M if the cell is the one Marlin is currently at, an uppercase N if the cell is the one Marlin's son is currently at and . if the cell is an unoccupied non-dangerous cell.

출력

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is IMPOSSIBLE if there is no program that would get Marlin to his son under the conditions explained above, or the smallest number of instructions in such a program.

제한

• 1 ≤ T ≤ 100.
• A_ij is either #, ., uppercase M or uppercase N, for all i and j.
• A_ij = M for exactly one pair of i and j.
• A_ij = N for exactly one pair of i and j.

Test Set 1 (19점)

시간 제한: 30 초

• 1 ≤ R ≤ 10.
• 1 ≤ C ≤ 10.

Test Set 2 (30점)

시간 제한: 120 초

For at most 10 test cases:

• 1 ≤ R ≤ 100.
• 1 ≤ C ≤ 100.

For the remaining test cases:

• 1 ≤ R ≤ 50.
• 1 ≤ C ≤ 50.

힌트

Below are some shortest programs for each of the possible sample case.

• Sample Case #1:

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

  or

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

  .
• Sample Case #2:

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

  .
• Sample Case #3:

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

  .
• Sample Case #4:

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

  .

Notice that even though the program must contain the smallest possible number of lines, it is not required to minimize the number of moves that Marlin makes.