페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5211
스페셜 저지

발판밟기 1s 128MB

문제

정올 대륙을 여행하는 여행자는 수수께끼를 풀어야 보물상자를 열 수 있는 장치를 발견했다. 

그 옆에 적혀있는 힌트는 다음과 같았다.

그리고 발판이 다음과 같이 주어져 있었다.

그리고 위 힌트를 이용하여 다음과 같이 순서를 맞추어 모든 발판을 밟았더니 보물상자를 열 수 있었다.

이러한 장치가 워낙 많아서 여행자는 너무 피곤해졌다. 여행자를 도와 수수께끼를 풀어주자.

발판의 크기가 워낙 커서 항상 바깥쪽 발판​부터 시작해야 하며, A, B, C 모두 시작점으로 가능하다.

상하좌우 1칸씩만 이동 가능하고 대각선으로 이동할 수는 없다.


입력

발판의 행 크기 R과 열 크기 C가 첫 번째 줄에 공백을 구분으로 주어진다. ( 1 \le R \le 9 ) ( 1 \le C \le 9 )

그 후 R줄에 걸쳐 C개의 문자가 공백을 구분으로 발판 상태가 주어진다. 문자는 A, B, C 3종류이다.


출력

각 발판을 밟는 순서를 발판 상태에 맞추어, R행에 걸쳐 C개의 숫자를 공백을 구분으로 출력한다.

가능한 경우가 여러가지일 경우 한가지 경우만 출력한다.

 불가능할 경우 impossible을 출력한다.


예제 #1

3 3

A B C

B C A

A C B
1 2 3

8 9 4

7 6 5

예제 #2

3 3

A B C

A B C

A B C
impossible

출처

eva
로그인해야 코드를 작성할 수 있어요.