|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||512 MB||1||0||0||0.000%|
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|
The first line of input will contain the number of test cases,
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+ +~~..+ +~~..+ +~~..+ ++++++