CDC12_G - Glory War

no tags 

Ronny is hiding on the building where he left his family after failing the guard test (the guard told him not to cheat and got angry after your help). The Rainbowlandians are brutally attacking the citizens of planet Earth, there are corpses everywhere and desperate people running on the street. Ronny must protect his family and that’s why he has decided to take down all the Rainbowlandians inside the building as soon as possible.

Ronny know very little about the Rainbowlandians, but he knows that he must be silent when he takes down one of then, hence, he hides his noisy gun in his pocket, impeding him to attack them from the distance. In order to take down the Rainbowlandians, a knife or a good flying kick will do the job. Ronny must step on the same space a Rainbowlandian is to take him down. The building is full of rubble and some paths will lead to a trap. Fortunately, Ronnie can throw a rope and go up or down through floors while he is walking the building. Obviously, he cannot throw the rope if this will lead him to a rubble-full step.

Given the dimensions of the building, its width, height and depth and the marked targets, you’re to make a program to help Ronny take down the Rainbowlandians in the minimum steps possible so he can do the minimum noise possible.

Please note that:

  • Ronny starts at the north west corner of the first floor of the building (1,1,1)
  • Ronny can only move to these possible directions: east, west, north, south, in addition, he can go while moving up or down.
  • Ronny cannot leave the building at any moment and there’s no basement in the building neither, so he can’t be lower than height 1.

Input

The first line contains an integer T, which specifies the number of test cases. Then, will follow the descriptions of T test cases.

Each test case will start with two integers N and H, where N denotes the width and depth of each floor and H denotes the number of floors. Then, there will be H N×N matrices, each one describing one floor. The floor description is composed of the following characters:

  • The character ’#’ denotes a rubble space.
  • The character ’.’ denotes a free space.
  • The character ’*’ denotes a Rainbowlandian.

Output

For each input case you must print the string "Scenario #i: " where i is the test case you’re evaluating (starting at 1), followed by the minimum steps that Ronny have to make to take down all the enemies inside the building. If this is impossible, print -1.

Sample

Input
3
2 1
..
.*
3 2
.#.
.##
##.
#.#
###
.#*
4 3
....
.##.
####
****
####
####
....
#.##
####
*..*
*..*
####

Output
Scenario #1: 2
Scenario #2: -1
Scenario #3: 13

Constraints

  • 1 ≤ T ≤ 30
  • 1 ≤ N ≤ 20
  • 1 ≤ H ≤ 20
  • 1 ≤ Targets ≤ 10

hide comments
ouyia: 2020-01-30 23:52:38

At least AC! Tricky backtracking

Last edit: 2020-03-03 12:20:28
Archit Mittal: 2012-12-16 06:33:51

GOT AC :)

Last edit: 2012-12-16 07:28:46
Ehor Nechiporenko: 2012-12-14 08:40:39

Hi @dexter, seems like Rony can move east, west, north, south. + also he can move up or down with those directions.
So totally he can move east, west, north, south, up+east, up+west, up+north, up+south, down+east, down+west, down+north, down+south

Archit Mittal: 2012-12-13 11:16:39

"Ronny can only move to these possible directions: east, west, north, south, in addition,he can go while moving up or down."

plz explain the directions he can go and also plz explain test case 3

Last edit: 2012-12-13 11:42:39
Ehor Nechiporenko: 2012-12-11 12:40:44

Can Ronny move strictly up or down, without moving east, west, north or south? Or Ronny should go to sibling cell on next floor?

Archit Mittal: 2012-12-09 05:42:59

can ronny move in between consecutive floors or between any floors

A. Muh. Primabudi: 2012-12-07 18:18:58

@edward
• Ronny starts at the north west corner of the first floor of the building (1,1,1)

and there is no cases which (1,1,1) is '#'

Gregorius Edward: 2012-12-06 01:40:51

@problem setter : From which position did Ronny start? I mean which one is the first floor? And is it possible that the northwest corner of the first floor is "#"?


Added by:Venezuelan Programming League
Date:2012-10-27
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem used for UCV-CEIDEC contest.