Woburn Challenge 1999 - Suicidal

Good Hunting Will

So if you'll remember, both Ethan Hunt and Will Hunting are janitors at this college and since their collective genius has been untapped, they are coming up with a game to decide who is smarter. One of the them will run through a maze to find the other person in the shortest possible time. If you've ever toured Scarborough Campus, you will appreciate that it can in fact be a maze sometimes.

In addition, it is of note that this is a fairly modern college -- so modern in fact is the college that there are teleporters scattered throughout the school. Every teleporter is in 2 parts -- when you step into 1 part, you are teleported into the other part (from here on, "teleporter" refers to both parts in total).

Each teleporter is controlled by a switch located somewhere in the college. When the switch is activated, the teleporter it is associated with is turned on for a specific period of time (ie. a certain number of moves on your part) after which it is turned off again. A switch is located in the hallway and is turned on when you walk on it. If you step on a switch to a transporter that has already been activated, you reset its time. Every transporter has exactly 1 switch controlling it.

The teleporters are part of the walls. When you walk into a teleporter that is activated, you are instantaneously (ie. At no time cost), transported to your destination which is the other half of the same teleporter. So, your only cost to teleporting is the 1 step it takes you to step onto the teleporter -- you instantly materialize on the other teleporter. Note that if a teleporter is not activated, it behaves just like a wall and if it is activated and you step into it, you will be transported.

You will start from a location and you will be given the ending location where Ethan will be. You need to get to Ethan in the least amount of time. Note that it may not be possible to get to Ethan, in which case you output "IMPOSSIBLE". If it is possible, you output the least number of steps you need to take to reach Ethan. Note that it takes 1 step to step into the exit.

Input

Line 1 : Number of input sets

The 1st line of the input sets will consist of m n where m is the number of rows in the maze and n is the number of columns (m,n ≤ 100).
The 2nd line contains the length of time that each teleporter is activated for (all teleporters have the same length of time that they are activated for).

Then, you will be given a mxn maze with the following legend. Every block can either be a "W", " "(1 blank space), "X", "Y", "a" to "t" or "A" to "T".

W = Wall
X = Starting location
Y = Finishing location
" " = Empty space to walk in
a-t = Teleporters. Each teleporter is given a unique designation from "a" to "t". Both halves of the teleporter are given the same designation.
A-T = Switches. Switch A controls teleporter 'a' and so on.

Output

For each test case, output the least amount of time in which Ethan can reach the finishing location, and "IMPOSSIBLE" otherwise

Sample Input

1
8 10
5
WWWWWWWWWW
W W bW   W
Y a  WX  W
W W  WWAaW
W     b  W
W  WW BWWW
W  W  W  W
WWWWWWWWWW

Sample Output

5

All Submissions
Best Solutions


Point Value: 20 (partial)
Time Limit: 10.00s
Memory Limit: 256M
Added: Oct 19, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I removed the stupidly unsolvable last case, so now all of the cases are well under the bounds, and this problem can actually be solved reasonably.

What is the range of the length of activation time of each teleporter?
What is the max number of inputs in each test case?

Thanks.

Activation times will be less than 100, and there are about 2-3 cases per file.

Thank you, though I'm still at O(50 trillion). :D