頁面無法載入？點擊這裡可能會修復。
Placeholder

#10465

헤이 구글, 운전해! 60s 2048MB

問題

구글 어시스턴트(Google Assistant) 팀과 안드로이드 오토(Android Auto) 팀이 음성 명령으로 운전할 수 있는 새로운 프로토타입 자동차를 함께 만들고 있다. 초기 프로토타입은 자동차 시뮬레이터에 연결된 휴대폰을 통해 동작한다. 그런데 불행히도 초기 테스터 중 한 명이 휴대폰을 변기에 떨어뜨려 마이크가 고장 나는 바람에, 새 기능을 사용하기가 더 어려워졌다. 그래도 이 기회를 놓치고 싶지 않아서, 어떻게든 사용하기 위해 당신의 도움이 필요하다.

초기 프로토타입은 \mathbf{R}행 \mathbf{C}열의 단순한 격자 위에서 움직이며, 북(north), 남(south), 동(east), 서(west)라는 4가지 아주 단순한 음성 명령만 이해한다. 각 명령은 차가 해당 방향으로 정확히 한 칸 이동을 시도하게 만든다. 하지만 마이크 문제 때문에, 시스템은 북과 남을 서로 혼동할 수 있고, 또 별도로 동과 서도 서로 바꿔 들을 수 있다. 즉 north 명령을 내리면 북 또는 남으로 움직일 수 있고, south 명령을 내리면 남 또는 북으로 움직일 수 있으며, east와 west도 마찬가지로 둘 중 어느 쪽으로든 움직일 수 있다. 모든 경우에서 두 가지 이동 결과는 같은 확률(1/2)로 발생한다.

테스터는 각 칸이 벽(wall)이거나, 위험(hazard)이거나, 혹은 비어 있도록 격자를 구성했다. 어떤 명령이 차를 벽으로 이동시키거나 격자 밖으로 나가게 한다면, 대신 아무 일도 일어나지 않는다. 어떤 명령이 차를 위험 칸으로 이동시키면, 차는 그 이후로는 더 이상 어떤 명령도 실행할 수 없다.

테스터는 빈 칸들 중 일부를 '흥미로운 출발점(interesting starts)'으로, 다른 일부를 '흥미로운 도착점(interesting finishes)'으로 표시해 두었다. 어떤 흥미로운 출발점과 흥미로운 도착점의 쌍이 운전 가능(drivable)하다는 것은, 출발점에서 시작해 음성 명령으로 차를 운전하여, 도착점에서 끝날 확률이 최소 1 - 10^{-{10^{100}}}가 되도록 하는 전략이 존재한다는 뜻이다. 전략은 이전 명령들의 결과에 따라 어떤 명령을 내릴지, 그리고 언제 멈출지를 선택할 수 있다. 차가 위험 칸으로 들어가면 그 즉시 움직임을 멈추므로 도착점에 도달할 수 없다는 점에 유의하라. 테스터는 모든 운전 가능한 쌍의 목록을 구하는 데 당신의 도움이 필요하다.


輸入

입력의 첫 줄에는 테스트 케이스 수 \mathbf{T}가 주어진다. \mathbf{T}개의 테스트 케이스가 이어진다. 각 테스트 케이스는 정수 두 개 \mathbf{R}, \mathbf{C}로 시작하며, 이는 격자의 행 수와 열 수이다. 그 다음 \mathbf{R}줄이 이어지며, 각 줄에는 길이가 \mathbf{C}인 문자열이 하나씩 주어진다. 이 중 i번째 줄의 j번째 문자 \mathbf{G_{i,j}}는 i행 j열의 칸을 다음과 같이 나타낸다.

  • 마침표(.)는 흥미롭지 않은 빈 칸을 나타낸다.
  • 샵 기호(#)는 벽이 있는 칸을 나타낸다.
  • 별표(*)는 위험 칸을 나타낸다.
  • 영문 소문자(a부터 z)는 흥미로운 출발점인 빈 칸을 나타낸다.
  • 영문 대문자(A부터 Z)는 흥미로운 도착점인 빈 칸을 나타낸다.


輸出

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, 운전 가능한 쌍이 하나도 없다면 y는 NONE이어야 한다. 그렇지 않다면 y는 공백으로 구분된 길이 2의 문자열들의 열이어야 하며, 각 문자열은 운전 가능한 쌍을 나타내고 첫 문자는 출발점의 문자, 두 번째 문자는 도착점의 문자를 뜻한다. 모든 운전 가능한 쌍을 알파벳 순서로 출력하라.


範例 

4
1 2
aZ
4 4
a..c
**.*
.Y.#
bX#Z
2 2
a*
*Z
2 7
a*bcd*.
...*F#.
Case #1: aZ
Case #2: aY bX bY cY
Case #3: NONE
Case #4: dF
샘플 케이스 #1에서는 결승점에 도달할 때까지 서쪽 명령을 반복하는 전략이 가능하다. 매번 결승점에 도달할 확률이 1/2, 같은 위치에 남을 확률이 1/2이다. 따라서 10^{101}번 이하의 이동에서 결승점에 도달하지 못할 확률은 2^{-10^{101}} \lt 10^{-10^{100}}이다. 샘플 케이스 #2에서는 샘플 케이스 #1과 비슷한 전략으로 위에서 첫 번째 줄 (1)의 어떤 위치에서든 다른 위치로 원하는 만큼 높은 확률로 이동할 수 있고, 위에서 세 번째 줄의 모든 비벽 위치 (2)에서도 마찬가지다. 또한 남쪽 명령을 사용하면 왼쪽에서 세 번째 열 (3)의 비벽 위치 사이를 이동할 수 있다. a와 c에서는 (1)을 이용해 왼쪽에서 세 번째 열로 이동한 다음 (3)을 이용해 Y 바로 옆까지 이동하고, (2)를 이용해 Y로 이동하면 aY와 cY가 모두 이동 가능해진다. 그러나 세 번째 줄에서 북쪽이나 남쪽 명령을 안전하게 사용할 수 있는 곳은 세 번째 열뿐이며, 그렇지 않으면 차가 위험 구역으로 들어갈 수 있다. 따라서 세 번째 줄에서 네 번째 줄로 안전하게 이동할 방법이 없어 aX와 cX는 이동 불가다. 반면 b에서는 비슷한 전략으로 X에 도달할 수 있고, X에서 북쪽이나 남쪽 명령을 반복해 Y에 도달할 수 있다(위쪽의 위험 구역으로 들어가지 않고 Y에 도달하면 중지한다). 마지막으로 결승점 Z는 완전히 고립되어 있으므로 이동 가능한 쌍에 포함될 수 없다. 샘플 케이스 #3에서는 흥미로운 시작점에서 흥미로운 도착점까지의 모든 경로가 위험 구역을 지나므로 해당 쌍은 이동 불가다. 샘플 케이스 #4에서는 흥미로운 시작점 d만이 결승점 F에 도달할 수 있는 전략을 가진다.

來源

GCJ 2023d C

需要登入才能撰寫程式碼。