문제
주차의 달인 택쌤은, 주차장에서 어떤 차 밑에 아기 고양이가 자고 있는 것을 목격했다.
가만히 내두면 아기 고양이가 위험하기 때문에,택쌤은 아기 고양이를 안전한 곳으로 옮기려고 한다.
아기 고양이를 구하기 위해선, 우선 아기 고양이가 위치한 공간에 있는 차를 움직여서 그 공간을 비워야 한다.
주차장에는 1x2크기의 차들이 가로 혹은 세로로 주차되어 있다.
이 주차장은 단 한 곳, 1x1크기의 빈 공간이 있으며, 이를 이용해 차들을 움직여서 새로운 빈 공간을 만들어내야 한다.
어떤 공간은 장애물이 위치하여, 아예 차가 못 움직이기도 한다.
다음 그림을 보자.
3번 차 밑에 있는 검은색 공간이, 아기 고양이의 위치이다.
고양이를 구출하기 위해선, 차 8을 움직여서 (1,1)에 빈공간을 만들고, 그 빈공간으로 다시 차 4를 움직여서 (3,1)에 빈공간을 만들고, 마지막으로 3을 움직이면 된다.
(3,4)에 위치한 X는 장애물을 뜻한다.
주차장의 상태가 주어졌을 때, 움직여야 하는 차의 번호를 순서대로 출력하는 프로그램을 작성하라.
입력
첫 줄에 주차장의 가로와 세로의 크기인 n과 m이 주어진다(1<= n<=250, 1<=m<=250).
다음 n줄에 걸쳐서 m개의 정수(-2 이상 62,500이하)가 주어지며, 이는 각 칸의 상태를 나타낸다.
0이상의 정수가 주어질 경우, 그 칸에 해당 번호의 차가 있다는 뜻이며, -1이 주어진 경우 빈 공간을 뜻한다.
빈 공간은 주차장에 하나만 존재한다. -2이 주어질 경우 장애물이 위치해 있음을 뜻하며, 장애물은 여러 개 존재할 수 있다.
차 번호가 주어진 경우, 항상 같은 번호가 2개, 가로 혹은 세로방향으로 인접해 있으며, 같은 번호의 차가 두 개 이상 존재하는 경우는 없다.
마지막 줄에 고양이의 위치인 r과 c가 주어진다(1<=r<=n, 1<=c<=m).
출력
첫 째 줄에 옮겨야 하는 차 번호를 순서대로, 공백으로 구분하여 출력한다.
여러 가지 방법이 존재할 경우, 가장 적은 횟수로 차를 옮기는 방법을 선택한다.
어떤 방식으로도 아기 고양이를 구출할 수 없는 경우는 impossible을 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10점 | 차는 모두 가로 방향으로만 주차되어 있다. |
| #2 | 20점 | 해당 주차장에는 장애물이 없다. |
| #3 | 45점 | n<=10,m<=10 |
| #4 | 25점 | 주어진 제약조건 외 아무런 제약조건이 없다. |
예제 #1
4 4
8 8 -1 9
4 10 10 9
4 3 3 -2
16 16 2 2
3 3
8 4 3
예제 #2
4 4
8 8 -2 9
4 10 10 9
4 3 3 -1
16 16 2 2
3 3
impossible
로그인해야 코드를 작성할 수 있어요.