7 - Chuck's Challenge
Chuck's Challenge is a game in which a player navigates a maze consisting of various tiles in a grid. The player can encounter doors that may be unlocked using keys they acquire along the way. You must write a program to determine the minimum number of doors that must be opened to reach the exit of the maze.
|~||Unstable floor||See rules|
- Tiles that are diagonal to each other are not considered to be adjacent (only up, down, left, and right).
- The player begins the maze visiting the entrance tile.
- The player may only visit passable tiles that are adjacent to the tile the player is currently visiting.
- Doors are considered impassable until a tile with a matching key ('A' matches 'a', 'B' matches 'b', etc.) has been visited.
- At first, unstable floors are considered passable; however, if the player leaves an unstable floor and visits any other type of tile, it becomes impassable.
- When an unstable floor tile becomes impassable, all adjacent unstable floor tiles become impassable.
- The external edge of the maze is an impassable wall.
The first line of input will contain the number of test cases, T (1 <= T <= 50). Each test case will begin with a line containing two integers R C (4 <= R, C <= 50). Following that will be a maze with R rows and C columns. Only the characters in the key will be present in the maze.
Each test case will have a single line of output. Print the minimum number of doors that must be opened to reach the exit or print "Impossible" if the exit cannot be reached.
2 8 15 +++++++++++++++ +>............+ +...a...+~+~+B+ +~+++++++~+~+.+ +~++..b..C+~+.+ +~++A++++++~+.+ +....~~~~~~c+<+ +++++++++++++++ 8 6 ++++++ +>.A<+ +.++++ +.+.a+ +~~..+ +~~..+ +~~..+ ++++++