미로 늘이기

보통 미로에서의 경로 길이는 시작 지점에서 끝 지점까지 밟은 걸음의 수로 측정하며, 한 걸음의 거리는 정확히 1이라고 본다. 이제 미로를 세로 방향(남북)으로 늘이거나 줄일 수 있다고 하자. 늘이거나 줄이는 것은 세로로 인접한 두 칸 사이 한 걸음의 이동 거리만 바꾼다. 즉, 그런 한 걸음의 거리가 1 대신 $X$가 된다. 가로 방향(동서) 한 걸음의 거리는 항상 1이다.

미로는 2차원 격자이며, #은 벽, S는 시작 칸, E는 끝 칸을 나타내고, 나머지 칸은 모두 지나갈 수 있다. 상하좌우로 인접한, 지나갈 수 있는 칸 사이를 이동할 수 있다.

외부 사정 때문에 S에서 E까지의 최단 경로 길이를 정확히 $L$로 만들어야 한다. 미로의 배치는 바꿀 수 없고, 가로 방향으로는 아무것도 바꿀 수 없다. 오직 세로 방향만 임의의 비율로 늘이거나 줄일 수 있다.

늘임 비율 $P$는 세로 한 걸음의 거리를 백분율로 나타낸 값이다. 즉, 세로 한 걸음의 거리는 $P / 100$이다(따라서 $X = P / 100$). 미로의 최단 경로가 정확히 $L$이 되도록 하는 비율 $P$를 구하라.

첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스는 두 수 $L$과 $N$이 적힌 줄로 시작한다. 여기서 $L$은 요구되는 최단 경로 길이이고, $N$은 미로를 설명하는 줄의 수이다. 이어지는 $N$개의 줄이 미로를 한 줄에 한 행씩 설명한다. 각 줄의 길이가 미로의 가로 크기이다.

각 테스트 케이스마다 늘임 비율을 다음 형식으로 출력한다.

Case #K: P%

여기서 K는 1부터 시작하는 테스트 케이스 번호이다. $P$의 값이 0과 1 사이이면 앞에 0을 붙여야 한다. $P$는 소수점 아래 넷째 자리에서 반올림하여 셋째 자리까지 나타내고, 항상 소수점 아래 셋째 자리까지 출력한다(필요하면 뒤에 0을 채운다).

미로의 높이와 너비는 각각 최대 100칸이다.

하나의 미로를 설명하는 모든 줄의 길이는 같다.

항상 해가 존재한다.

결과는 0.000 이상 1000.000 이하이다.

S와 E를 가로 이동만으로 잇는 경로는 결코 존재하지 않으며, 따라서 결과는 항상 유일하다.

최단 경로가 가로 두 걸음과 세로 한 걸음으로 이루어져 자연스러운 길이가 3인 미로를 생각해 보자. 최단 경로 길이를 2.5로 만들려면 세로 한 걸음의 거리가 0.5가 되어야 하고, 이는 세로 방향을 50%로 늘인(줄인) 것에 해당한다.