cho.sh

Map Reduce (Small)

벽으로 둘러싸인 격자에서 시작점과 도착점이 주어질 때, 벽을 제거해 최단 경로 길이를 정확히 D로 만들 수 있는지 판정하고, 가능하면 정해진 탐욕 제거 절차로 만든 격자를 출력한다.

어려움8BFS시뮬레이션그리디그래프아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

비디오 게임 디자이너 벤은 곧 나올 증강 현실 모바일 게임의 지도를 만들고 있다. 최근 만든 지도는 RR개의 행과 CC개의 열로 이루어진 격자이다. 각 칸은 빈 칸을 뜻하는 ., 지나갈 수 없는 벽을 뜻하는 #, 하나뿐인 출발 위치 S, 하나뿐인 도착 위치 F 중 하나이다. 예를 들어 지도는 다음과 같을 수 있다.

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

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

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

  • 임의의 두 빈 칸 사이에 경로가 있다. 출발 위치와 도착 위치도 빈 칸으로 친다.
  • 구조가 튼튼하려면 벽끼리 꼭짓점만이 아니라 변으로 맞닿아야 한다. 지도의 모든 2×22 \times 2 영역에 대해, 그 영역에 벽이 정확히 두 개 있으면 두 벽은 같은 행이나 같은 열에 있다. 즉 벽이 아래 두 가지 배치 중 하나로 놓인 2×22 \times 2 영역은 없다.
#.   .#
.#   #.
  • 경계는 모두 벽이다. 맨 위 행, 맨 아래 행, 맨 왼쪽 열, 맨 오른쪽 열에 있는 칸이 경계이다.

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

벤은 이 지도가 친구들에게 너무 어렵다는 것을 깨닫고, 벽 몇 개를 없애 난이도를 낮추려고 한다. 벽을 0개 이상 없애서, 결과 지도가 여전히 좋은 지도이면서 출발 위치에서 도착 위치까지 최단 경로의 길이가 정확히 DD가 되게 할 수 있는지 알고 싶다. 길이가 DD인 경로가 있는 것만으로는 부족하고, 최단 경로의 길이가 DD여야 한다.

예를 들어 D=15D = 15이면 도착 위치 바로 아래의 벽을 없애서 최단 경로의 길이가 15인 좋은 지도를 얻을 수 있다.

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

D=5D = 5이면 방법이 없다.

입력

첫째 줄에 테스트 케이스의 수 TT가 주어진다. 이어서 TT개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 세 정수 RR, CC, DD가 공백으로 구분되어 주어진다. 각각 지도의 행 수, 열 수, 벽을 없앤 뒤 원하는 최단 경로의 길이이다. 다음 RR개의 줄에는 벤의 지도가 한 줄에 CC개의 문자(., #, S, F)로 주어진다.

주어지는 지도는 항상 좋은 지도이다.

제한

  • 1≤T≤1001 \le T \le 100
  • 각 테스트 케이스에는 S와 F가 정확히 하나씩 있다.
  • 입력 파일의 크기는 3MB 이하이다.
  • 3≤R≤403 \le R \le 40
  • 3≤C≤403 \le C \le 40
  • 1≤D≤16001 \le D \le 1600

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 POSSIBLE 또는 IMPOSSIBLE이다. 벽 몇 개를 없애서 지도가 여전히 좋은 지도이면서 최단 경로의 길이가 정확히 DD가 되게 할 수 있으면 POSSIBLE, 없으면 IMPOSSIBLE이다.

답이 POSSIBLE이면 이어서 아래 절차로 얻은 지도를 CC개의 문자로 된 RR개의 줄에 출력한다. 없앤 벽은 .로 바꿔 쓴다.

현재 지도에서 최단 경로의 길이를 LL이라 하자. 칸의 순서는 위쪽 행이 먼저이고, 같은 행에서는 왼쪽 칸이 먼저이다. 경계에 있지 않고, 그 벽 하나만 없앴을 때 지도가 여전히 좋은 지도인 벽을 후보라고 부른다. L≠DL \ne D인 동안 다음을 반복한다.

  1. 없앴을 때 LL이 정확히 2 줄어드는 후보가 있으면, 그런 후보 중 칸의 순서로 가장 앞선 벽을 없앤다.
  2. 그런 후보가 없으면, 없애도 LL이 변하지 않는 후보 중 칸의 순서로 가장 앞선 벽을 없앤다.

처음 주어진 지도에서 L=DL = D이면 벽을 하나도 없애지 않는다. 이 문제에서 답이 POSSIBLE인 모든 테스트 케이스에서 이 절차는 항상 L=DL = D에 도달한다.

힌트

예제 1은 문제 설명의 예시이다. 도착 위치 바로 아래의 벽을 없애도 최단 경로의 길이가 15가 되지만, 도착 위치 바로 왼쪽의 벽이 칸의 순서로 더 앞서고 이 벽을 없애도 최단 경로가 2 줄어든다. 따라서 절차는 이 벽을 없앤다.

예제 2에서는 벽을 없애 최단 경로의 길이를 2나 4 등으로 만들 수 있지만, 정확히 3으로 만들 방법은 없다.

예제 3에서는 처음부터 최단 경로의 길이가 11이므로 벽을 없앨 필요가 없다.