HIPPO - Hippo and Bloody Jungle

no tags 

Background

Hippo and his two friends lost their path in a jungle. In this days jungle is most dangerous place. The jungle has lots of tunnels. Also there lived some brutal animals in the dangerous zone (the cell ‘D’). Now Hippo and his two friends want to go to safe places (‘#’) as fast as possible i.e. in minimum times.

Problem

In this problem you are given the jungle-map as a grid. Where ‘A’, ’B’, ’C’ denotes the position of Hippo and his two friends. ’D’ indicates dangerous place. No one can stay this cell. ‘#’ denotes the safe place. In this grid there are also given some characters (E-Z) which occur more than one and denotes if one reaches a tunnel he can go any other tunnel of same character and also any adjacent cell (8 directions). They also can move any adjacent cell from ordinary place. Each move takes 1 unit of time. Is it possible to go all of them to safe places? If possible then what is the minimum time required.

Input

Input starts with an integer T (≤ 15), denoting the number of test cases.

Each case starts with a line containing two positive integers H and W; W and H are the numbers of cells in the x and y directions, respectively. W and H are not more than 20. There will be H more lines in the data set, each of which includes W characters. Each character represents the status of a cell as follows.

  • '.' – ordinary place.
  • '#' – safe place.
  • 'A', 'B', 'C' - initial position of Hippo and his friends.
  • 'D' – Dangerous place.
  • 'E' - 'Z' - denote the tunnel.

Output

For each test case, print the case number and minimum time if it is not possible to reach all of them into safe position otherwise print “impossible” without quote.

Example

Input:
2
5 6
C..E#.
.D....
F..E..
.D..A.
.B.D.F
4 4
C.D#
.FDD
A..E
.B.F

Output:
Case 1: 4
Case 2: impossible

Problem Setter: Md Abdul Alim, Dept. of Computer Science, Bangladesh University of Business and Technology


hide comments
nadstratosfer: 2019-02-09 13:37:10

There is exactly one safe place in the grid, but there might be 1 or more than 2 tunnel entrances marked with the same letter! Not only that, there are random linebreaks WITHIN the grid lines >:0! You need to read chunks until they add up to W-long line. Finally statement defines the result poorly, we're looking for maximum of shortest paths from (A, B, C) to #. The guesswork needed to get through all the stupidity needed far more effort than solving the problem itself. -1.

Simes: 2019-01-30 09:42:51

Caution: there are blank lines between number of rows / columns and the map, or within the map itself. I got so many NZECs because of this. Bah! Thumbsdown for that.

The problem doesn't say there's only one safe place, but testing on Spojtoolkit suggests that's the case.

fitcat: 2014-08-06 11:35:17

My AC solution output impossible for the first test case from Shipu Ahamed. I believe that test case is invalid as there are no friends ('B' and 'C') there.

(REPLY from BLANKRK): yes the test case is invalid .

Last edit: 2014-07-16 09:01:59
BLANKRK: 2014-08-06 11:35:17

OMG!! AC in 1st attempt..:D
feeling awesome !!
nice problem :P

Mitch Schwartz: 2014-08-06 11:35:17

Can two or more characters occupy the same non-safe cell at the same time? E.g. for test case

3 3
D#D
D.D
ABC

would the answer be 2 or 4?
RE-> answer should be 2

Another question: (maybe it can be inferred by examining the example I/O, but it should be stated (more) clearly in the description) Is traveling onto a tunnel opening considered one move, and traveling to another end of the tunnel considered another move? E.g. suppose we are only considering one character and the landscape looks like

AEE#

then I think it will take 3 moves for him to reach the safe place -- is that the right interpretation?

RE (Jacob): Yup, it takes one extra move to go from E-Z to another E-Z, so the answer is 3.

(Mitch) Thanks for the replies.

Last edit: 2014-07-15 18:57:08

Added by:Alim
Date:2014-06-15
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU