1 人解决，5 人已尝试。
1 份提交通过，共有 30 份提交。
9.9 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
The game of Bomb man is played on an m-by-n grid. Each cell of the grid is either a solid wall ('#'), a wooden crate ('x') or empty space ('.').
An important part of the game is destroying wooden crates to find powerups that are hidden inside. You do this by exploding bombs. These are the rules:
⑴You have an unlimited supply of bombs, but you may only explode one bomb at a time.
⑵Your are immune to your own bomb blasts.
⑶There is no opponent - you are alone in the maze.
⑷You may place a bomb only at your feet.
⑸Your bombs' blast radius is 1, which means that if you explode a bomb at maze location (i, j), it will trigger an explosion at the 4 neighbouring locations, unless those are walls or lie outside the maze.
⑹It takes you 1 second to move one square east, north, west or south, 1 second to set up us the bomb and 1 second to explode the bomb (which you may do with a remote controlled device, no matter where you are in the maze in relation to the bomb's location).
⑺You are not allowed to leave the grid at any time.
How many seconds will you need to explode all of the wooden crates?
The first line of input gives the number of cases, N. N test cases follow. Each one starts with a line containing m and n. The next m lines will each contain n characters, denoting a wall ('#'), a crate ('x'), an empty cell ('.') or your current position ('Y'). Assume that you start in an empty cell.
1 <= N <= 50,
1 <= m, n <= 20,
There will be at most 8 wooden crates in each maze.
For each test case, output a line containing “Case #x: y”, where x is the number of the test case and y is the minimum number of seconds you will need to destroy all the crates. If this is impossible to do, print -1 instead of y.
6 4 5 ##### #Y.x# #x.x# ##### 5 5 ##### #.x.# #xYx# #.x.# ##### 2 10 Y......... .........x 10 10 Y#.x.#.x.. .#.#.#.#.x .#.#.#.#.. .#.#.#.#.x .#.#.#.#.. .#.#.#.#x. .#.#.#.#.. .#.#.#.#x. .#.#.#.#.. .x.#.x.#.. 1 3 Y#x 1 3 Yxx
Case #1: 6 Case #2: 2 Case #3: 11 Case #4: 64 Case #5: -1 Case #6: 5 Hint: One possible way to solve example 1 in 6 seconds is as follows: ⑴Move 1 step east. ⑵Place a bomb there. ⑶Move 1 step south. ⑷Detonate the bomb, destroying the north-eastern crate. ⑸Place a bomb at your location. ⑹Detonate the second bomb, destroying both remaining crates. Note that it is illegal to place the second bomb at step 4 because then you would have more than one unexploded bomb on the ground at the same time. The output formats:Case□#d:□d "□" represent a whitespace
1 人解决，5 人已尝试。
1 份提交通过，共有 30 份提交。
9.9 EMB 奖励。
创建: 16 年，5 月前.
修改: 7 年，2 月前.
最后提交: 12 年，5 月前.
来源: N/A