Checkpoint
면접 대비시간 제한1초메모리 제한1024 MB
격자 미로에서 S에서 E까지 이동하되 번호가 붙은 체크포인트를 오름차순으로 모두 들르는 최단 경로의 길이를 구해 출력한다.
문제
A drone is being tested by finding the shortest path through a maze, reaching every checkpoint on the way in order. Your task is to write a program that finds the shortest path from the start, through every checkpoint in order, and then to the exit, then prints the length of that path.
입력
The first line will contain a single integer n that indicates the number of data sets that follow. Each data set will start with three integers r, c, and d representing the number of rows and columns of the maze and the number of checkpoints, respectively. The next r lines will make up the maze, with S being the starting point, E being the end point, the numbers 1-9 being checkpoints, # being a wall, and . being an open space. S and E also count as open spaces.
출력
The output will be the length of the shortest path from the start, through every checkpoint in order, and to the exit. There will be n lines of output with no trailing whitespace.