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

#4376

Racing Car Trail 5s 128MB

문제

특정 암호 알고리즘에 대한 설명을 읽어 본 적이 있습니까? 이 설명들은 거의 항상 앨리스와 밥이 주고받는 메세지를 대상으로 한다. 우리(2011년 CERC를 조직한 사람들)는 그러한 설명들이 너무 비인격적이라고 생각한다 - 이 두 사람은 아마도 전 세계에서 가장 유명한 암호학자임에도 불구하고, 우리는 그들에 대해 거의 알지 못하기 때문이다. 그들은 더 많은 관심을 받을 자격이 있다고 생각한다. 예를 들어 우리는 그들의 취미에 대해 알아갈 수 있다.

 

 앨리스와 밥은 자유시간에 트론으로부터 영감을 받은 게임을 하는 것을 좋아한다. 그 게임이란 사각 격자에서 장난감 자동차 시합을 하는 것이다. 격자에는 장애물이 있어 차가 장애물에 부딪히는 것을 피해야만 한다. 또한, 자동차는 이미 방문했던 격자를 다시 지나갈 수 없다. 차는 4개의 인접한 방향(동, 서, 북 또는 남)으로만 움직일 수 있다. 앨리스와 밥은 번갈아 차를 움직인다. 앨리스가 시동을 걸고, 차를 초기 위치에서 그리드의 인접 위치 중 하나로 이동시킨 다음, 밥이 턴을 받아 차를 인접한 다른 위치로 이동시킨다.

 

 

 

 

 차를 충돌시킨 사람(즉, 장애물이 있는 위치로 이동하거나 이전에 방문한 위치 중 하나로 이동한 사람)은 게임에서 패배한다. 앨리스와 밥 둘 다 믿을 수 없을 정도로 이 게임에 뛰어난 사람들로, 절대 실수를 하지 않는다. 예를 들어, 그들은 충돌을 피할 수 없는 경우에만 차를 충돌시킨다. 장애물의 지도를 볼 때, 당신의 임무는 모든 초기 위치에 대해 어떤 사람이 이기는 지 구하는 것이다.​ 


입력

입력에는 여러 테스트케이스로 주어진다. 각 테스트케이스의 첫 번째 줄에는 행의 개수 N과 열의 개수 E(1 ≤ N,E ≤ 100)가 주어진다. 

 

다음 N개의 줄에는 게임판이 N행 M열의 글자 배열로 주어진다. i번째 행, j번째 열에 있는 문자는 게임판의 i번째 행, j번째 열 격자칸의 상태를 의미한다. 문자는 위치가 비어 있으면 "." (점)으로, 장애물이 있으면 "X"으로 주어진다. 게임판 바깥으로 나가는 것은 금지되어 있다.

 

 가장 마지막 테스트케이스는 0 0으로 주어지며, 이 테스트케이스에서는 아무것도 출력하지 않아야 한다.

 


출력

각 테스트케이스에 대해, E개의 글자로 이루어진 N개의 줄을 출력하여야 한다.

i번째 행, j번째 열에 출력해야 하는 문자는 다음과 같다. 

i번째 행, j번째 열에서 게임을 시작했을 때 앨리스가 이기면 ‘A’, 밥이 이기면 ‘B’, 장애물이 있으면 ‘X’를 출력한다.

 

 테스트케이스 사이에는 빈 줄을 출력해야 한다.​ 


예제

1 1

.
3 3
...
.X.
...
1 4
....
3 3
X.X
...
X.X
5 8
........
.XX.XXX.
.X..X...
.X.XX.X.
........
0 0
B


AAA
AXA
AAA

AAAA

XBX
BAB
XBX

BABABABA
AXXBXXXB
BXBAXABA
AXAXXBXB
BABABABA
로그인해야 코드를 작성할 수 있어요.