팩맨
시간 제한1초메모리 제한1024 MB
10x10 격자의 주어진 시작 칸에서 출발해 10000걸음 이내로 100개 칸을 모두 방문하는 경로를 출력한다.
문제
팩맨은 1980년대에 개발된 미로 추격 비디오 게임이다. 플레이어는 캐릭터 “팩맨”을 조종해 미로에 있는 점을 먹으면서 적 캐릭터 “유령”을 피한다. 모든 캐릭터는 위, 아래, 왼쪽, 오른쪽 네 방향으로 움직일 수 있다. 다음 두 조건 중 하나가 만족되면 게임이 끝난다.
- 팩맨이 미로의 점을 모두 먹는다. 이 경우 플레이어가 이긴다.
- 유령이 팩맨을 잡는다. 이 경우 플레이어가 진다.
그림 1: 팩맨 게임 플레이 (이미지 출처: Wikipedia)
Adam은 최신 프로그래밍 도구로 게임을 만드는 방법을 배우고 있다. 실력을 기르기 위해 그는 팩맨 게임을 조금 바꿔서 재현하려고 한다. Adam의 게임에서는 플레이어가 조종하는 캐릭터가 “유령”이고, 적 캐릭터가 “팩맨”이다. 유령과 팩맨의 역할을 바꿨으므로 게임 종료 조건도 바꾼다.
- 팩맨이 미로의 점을 모두 먹는다. 이 경우 플레이어가 진다.
- 플레이어가 조종하는 유령이 팩맨을 잡는다. 이 경우 플레이어가 이긴다.
Adam은 첫 번째 완성 버전을 거의 개발했다. 그는 게임을 시험하려고 간단한 스테이지를 만든다. 스테이지의 미로는 10×10 격자를 바탕으로 한다. r행과 c열이 교차하는 칸을 (r, c)라고 표기한다. 이 문제에서 행과 열은 0부터 9까지 번호가 매겨진다. 각 격자 칸에는 점이 정확히 하나씩 있다. 격자의 바깥 경계는 벽이다. 어떤 캐릭터도 격자 밖으로 움직일 수 없다. 격자 안에는 벽이나 장애물이 없다. 모든 캐릭터는 한 칸에서 인접한 칸으로 자유롭게 움직일 수 있다. 두 격자 칸 (r1, c1)과 (r2, c2)가 인접하다는 것은 |r1 − r2| + |c1 − c2| = 1인 경우와 그 경우뿐이다.
Adam은 시험을 위해 팩맨의 움직임을 준비해야 한다. 그는 다양한 팩맨의 이동 경로가 필요하지만, 어떤 경로든 다음 조건을 만족해야 한다.
- 팩맨이 그 경로를 따라가면 미로의 점을 모두 먹는다.
- 팩맨은 최대 10000번 움직인다.
Adam은 (x, y) 칸에서 시작하는 경로를 생성하는 데 도움이 필요하다. 위의 모든 조건을 만족하고 (x, y) 칸에서 시작하는 팩맨의 경로를 생성하는 프로그램을 작성하시오.
입력
입력은 정확히 한 줄이며, 공백으로 구분된 두 정수 x와 y로 이루어진다. (x, y) 칸에서 시작하는 경로를 생성해야 한다.
출력
요청된 경로를 다음 형식으로 출력해야 한다. 경로는 m + 1개의 줄로 표현되며, m은 경로의 이동 횟수이다. i번째 줄에는 공백 하나로 구분된 두 정수 ri와 ci가 들어간다. 경로는 (r1, c1) 칸에서 시작하고, 1 < i ≤ m + 1인 i에 대해 팩맨은 경로를 따라 i − 1번 움직인 뒤 (ri, ci) 칸에 있다.
답이 여러 개라면 아무거나 출력해도 된다.
제한
- m ≤ 10000
- 모든 i ∈ {1, 2, . . . , m + 1}에 대해 x, y, ri, ci ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}이다.
- 모든 i ∈ {1, 2, . . . , m}에 대해 칸 (ri, ci)와 (ri+1, ci+1)은 서로 인접하다.
- {(r1, c1)} ∪ {(r2, c2)} ∪ · · · ∪ {(rm+1, cm+1)} = {(r, c) : r ∈ {0, 1, . . . , 9}, c ∈ {0, 1, . . . , 9}}