#P13128. [GCJ 2019 Finals] Go To Considered Helpful
[GCJ 2019 Finals] 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 rows and 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:
- : move one cell North (up),
- : move one cell South (down),
- : move one cell West (left),
- : move one cell East (right), and
- : 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
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 instructions must jump to existing lines in the program.
输入格式
The first line of the input gives the number of test cases, . test cases follow. Each test case starts with a line containing and , the number of rows and columns in the matrix. Then, lines follow containing a string of characters each. The -th character of the -th of these lines represents the cell in the -th row and -th column of the matrix. The character is if the cell is dangerous, an uppercase if the cell is the one Marlin is currently at, an uppercase 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 is the test case number (starting from 1) and is 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.
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
提示
Sample Explanation
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)
Sample Explanation
- .
- is either , , uppercase or uppercase , for all and .
- for exactly one pair of and .
- for exactly one pair of and .
Test set 1 (19 Pts, Visible)
- Time limit: 30 seconds.
- .
- .
Test set 2 (30 Pts, Hidden)
- Time limit: 120 seconds.
- For at most 10 test cases:
- .
- .
- For the remaining test cases:
- .
- .