맵 리듀스 (Large)

뛰어난 비디오 게임 디자이너 벤은 곧 출시할 증강 현실 모바일 게임의 지도를 설계하고 있다. 최근 벤이 만든 지도는 R행 C열의 행렬이다. 지도는 빈 칸을 나타내는 . 여러 개, 지나갈 수 없는 벽을 나타내는 # 여러 개, 출발 위치를 나타내는 S 하나, 도착 위치를 나타내는 F 하나로 이루어진다. 예를 들어 지도는 다음과 같을 수 있다.

#############
#S..#..##...#
###.##..#.#F#
#...##.##.###
#.#.........#
#############

벤의 게임에서 경로란 벽을 지나지 않고 한 칸에서 다른 칸으로 가는 이동(위, 아래, 왼쪽, 오른쪽)의 나열이다.

벤은 다음 성질을 모두 만족하는 지도를 좋은 지도라고 부른다.

• 임의의 두 빈 칸(출발 위치와 도착 위치 포함) 사이에 경로가 있다.
• 구조가 무너지지 않도록 벽은 꼭짓점만이 아니라 변으로 맞닿아야 한다. 지도의 모든 2×2 영역에서 벽이 정확히 두 개라면 두 벽은 같은 행이나 같은 열에 있다. 다시 말해 벽이 다음 두 모양 중 하나로 놓인 2×2 영역은 없다.

#.    .#
.#    #.

• 경계는 벽으로만 이루어진다. 가장 위 행, 가장 아래 행, 가장 왼쪽 열, 가장 오른쪽 열에 있는 칸이 경계다.

최단 경로의 길이는 출발 위치에서 도착 위치까지 가는 데 필요한 최소 이동 횟수다. 위 예에서 최단 경로는 17번 이동한다.

영리한 지도 제작자인 벤은 이 지도가 친구들이 풀기에 너무 어렵다는 것을 깨달았다. 그래서 벽 몇 개를 제거해서 난이도를 낮추려 한다. 구체적으로 벽을 0개 이상 제거해서 출발 위치에서 도착 위치까지의 최단 경로가 정확히 D번 이동이 되고 결과 지도도 좋은 지도가 되게 할 수 있는지 알고 싶다. 길이가 D인 경로를 찾는 것만으로는 부족하며, 최단 경로의 길이가 D여야 한다.

예를 들어 D = 15이면 도착 위치 바로 아래의 벽을 제거해서 조건을 만족하는 지도를 얻을 수 있다.

#############
#S..#..##...#
###.##..#.#F#
#...##.##.#.#
#.#.........#
#############

D = 5이면 방법이 없다.

첫째 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 세 정수 R, C, D가 공백으로 구분되어 주어진다. R과 C는 지도의 행과 열의 수이고, D는 벽을 제거한 뒤 원하는 최단 경로의 이동 횟수다. 다음 R개의 줄에는 벤의 지도가 주어지며, 각 줄은 C개의 문자(., #, S, F 중 하나)로 이루어진다.

주어지는 지도는 문제에서 설명한 좋은 지도임이 보장된다.

제한

• $1 \le T \le 100$
• 각 테스트 케이스에는 S와 F가 정확히 하나씩 있다.
• 입력 파일의 크기는 3MB 이하이다.
• $3 \le R \le 1000$
• $3 \le C \le 1000$
• $1 \le D \le 10^6$

각 테스트 케이스마다 Case #x: y를 한 줄에 출력한다. x는 1부터 시작하는 테스트 케이스 번호이다. 벽을 제거해서 최단 경로가 D인 좋은 지도를 만들 수 있으면 y는 POSSIBLE이고, 그렇지 않으면 IMPOSSIBLE이다.

POSSIBLE이면 이어서 아래 절차로 만든 지도를 R개의 줄에 출력한다. 각 줄은 C개의 문자이며, 제거한 벽은 # 대신 .로 출력한다.

., S, F 칸을 빈 칸이라고 하자. 벽 칸 w가 다음 세 조건을 모두 만족하면 w를 제거 가능한 벽이라고 한다.

1. w는 경계에 있지 않다.
2. w를 .로 바꾼 지도가 좋은 지도다.
3. w의 위와 아래 칸이 빈 칸이고 왼쪽과 오른쪽 칸이 벽인 경우가 아니다. 또한 w의 왼쪽과 오른쪽 칸이 빈 칸이고 위와 아래 칸이 벽인 경우도 아니다.

절차는 벤의 지도에서 시작한다. 현재 지도의 최단 경로가 정확히 D이면 멈추고 현재 지도를 출력한다. 그렇지 않으면 현재 지도의 제거 가능한 벽 가운데 가장 위 행에 있는 것을 고르고, 그런 벽이 여럿이면 그중 가장 왼쪽에 있는 것을 골라 .로 바꾼 뒤 다시 확인한다. 답이 POSSIBLE인 경우 이 절차는 항상 최단 경로가 D인 지도에서 멈춘다. 벤의 지도의 최단 경로가 이미 D이면 지도를 그대로 출력한다.

첫 번째 예제 케이스는 문제 설명의 예다. 문제 설명에서 보인 지도(도착 위치 바로 아래 벽을 제거한 지도)도 최단 경로가 15인 좋은 지도이지만, 출력 절차는 벽 다섯 개를 제거한 다른 지도를 만들므로 그 지도를 출력해야 한다.

두 번째 예제 케이스에서는 예를 들어 벽을 제거해서 최단 경로를 2나 4로 만들 수 있다. 하지만 최단 경로를 정확히 3으로 만드는 방법은 없다.

세 번째 예제 케이스는 처음부터 최단 경로가 11이므로 벽을 제거할 필요가 없다.