시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 91 36 28 41.791%

문제

[그림] 슈퍼 메트로이드(1994) 지도

메트로베니아는 액션 게임의 하위 장르로, 메트로이드 + 캐슬배니아가 어원으로 이전에도 던전 탐색이 위주인 게임은 있었으나 그 기틀이 제대로 잡히고 대중의 인식에 각인된 것이 메트로이드와 악마성 시리즈이기에 이렇게 불린다. 메트로이드가 장르를 창시하였고, 캐슬배니아가 월하의 야상곡부터 메트로이드의 스타일을 이어받아 장르를 확립시켰기 때문이다. 게임 플레이에서는 평소에는 통과할 수 없던 지역과 샛길 등을 주인공의 성장과 능력 획득을 통해 그 탐색 활동의 저변을 확장하는 데에서 독특한 재미를 얻을 수 있도록 하는 데에, 게임 개발 측의 입장에서는 한정된 용량과 배경을 몇 배로 효율적으로 활용하면서 그러한 방식의 디자인을 설득력 있고 지루하지 않게 구조화하는 데에 의의가 있다.

국렬이는 메트로베니아를 정말로 좋아하기 때문에 택희 선배의 RPG Extreme의 후속작으로 Metroidvania Extreme을 제작하려고 한다. 다만 걱정할 것 없다. 전작이 너무 어려웠던 나머지 국렬이는 난도를 어마어마하게 낮추었다.

지도는 N × M으로 구성되어 있으며 각 문자는 다음을 의미한다.

  • # : 지나갈 수 없는 벽
  • @ : 시작점
  • * : 아무 것도 없는 곳
  • ! : 최종 목표 지점
  • a-z : 열쇠 아이템으로 해당 아이템이 있어야만 특정 구역에 진입할 수 있다. 해당 아이템을 획득할 시에 해당 알파벳의 대문자로 표기된 곳으로 이동할 수 있다.
  • A-Z : 자물쇠가 있는 지역이다. 해당 알파벳의 소문자로 표기된 열쇠 아이템을 얻어야 갈 수 있다.

Metroidvania Extreme의 규칙은 다음과 같다.

  • 주인공은 상하좌우로 인접한 곳으로 이동할 수 있다.
  • 주인공이 이전에 지나갔던 곳들은 순간이동을 통해서 바로 이동할 수 있다.
  • 벽이 있는 곳은 그 어떠한 경우에도 이동할 수 없다.
  • 맵 가장자리는 무조건 벽이다. 즉, 맵 밖으로 나갈 수 없다.
  • 최종 목표 지점에 도착하는 순간 지금까지 얻은 아이템의 개수와 전혀 상관없이 게임을 마무리 짓는다.
  • 아이템은 영구 아이템으로 절대로 소비하지 않는다. 즉, a라는 아이템을 1개만 획득하면 영구적으로 A 지역으로 이동할 수 있다.
  • 출발 지점과 목표 지점은 정확히 1개 있으며, 출발 지점에서 시작해 목표 지점까지 이동할 수 있음이 보장된다.

맵의 맨 왼쪽 위 칸을 (1,1), 오른쪽 아래 칸을 (N,M)으로 나타냈으며 판의 x번째 행, y번째 열에 위치한 곳을 (x,y)로 지칭한다.

Metroidvania Extreme을 시작했을 때, 끝날 때 까지 이동한 장소의 좌표를 순서대로 기록을 할 것이다. 단, 이전에 방문한 장소를 다시 방문했을 때는 다시 기록하지 않는다. 최종 목표 지점에 도달한 시점에서 최종 목표 지점의 좌표를 기록하고 마무리를 짓는다.

당신은 게임을 시작하려고 한다. 게임이 끝날 때 기록된 좌표들을 출력하여라. 답이 여러 개라면 아무 것이나 출력하여라.

입력

다음과 같이 입력이 주어진다.

N M
a1,1 . . . a1,M
. . . . . .
aN,1 . . . aN,M

출력

첫 번째 줄에는 지금까지 기록한 좌표의 수 k을 출력한다. 이후 k개의 줄에 걸쳐 기록한 순서대로 방문한 칸의 행 번호와 열 번호를 공백으로 구분하여 출력한다.

제한

  • 3 ≤ N, M ≤ 200
  • ai,j는 칸 (i, j)를 의미하며 알파벳 소문자 및 대문자, #, @, *, ! 중 하나다. (1 ≤ i ≤ N, 1 ≤ j ≤ M)

예제 입력 1

3 10
##########
#a**@**A!#
##########

예제 출력 1

8
2 5
2 6
2 4
2 7
2 3
2 2
2 8
2 9

예제 입력 2

3 16
################
#cFzOaB@bAoZfC!#
################

예제 출력 2

14
2 8
2 9
2 7
2 6
2 10
2 11
2 5
2 4
2 12
2 13
2 3
2 2
2 14
2 15

예제 입력 3

3 56
########################################################
#zyxwvutsrqponmlkjihgfedcba@ZYXWVUTSRQPONMLKJIHGFEDCBA!#
########################################################

예제 출력 3

54
2 28
2 27
2 26
2 25
2 24
2 23
2 22
2 21
2 20
2 19
2 18
2 17
2 16
2 15
2 14
2 13
2 12
2 11
2 10
2 9
2 8
2 7
2 6
2 5
2 4
2 3
2 2
2 29
2 30
2 31
2 32
2 33
2 34
2 35
2 36
2 37
2 38
2 39
2 40
2 41
2 42
2 43
2 44
2 45
2 46
2 47
2 48
2 49
2 50
2 51
2 52
2 53
2 54
2 55

예제 입력 4

7 7
#######
#a***!#
#*E*FG#
#*D***#
#*C***#
#@B***#
#######

예제 출력 4

10
6 2
5 2
4 2
3 2
2 2
2 3
2 4
2 5
3 4
2 6

예제 입력 5

7 7
#######
#!Z**c#
#C#*###
#bZ**Y#
#aaZ**#
#@aaB*#
#######

예제 출력 5

18
6 2
5 2
6 3
4 2
5 3
6 4
6 5
5 5
6 6
4 5
5 6
4 4
3 4
2 4
2 5
2 6
3 2
2 2