Informatica Online Judge

  숫자 매트릭스 [1189 / 04A5]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 23   Total Tried : 153


The Champion of this Problem (C++) : gs18105 - 0ms / 1413byte
My Best Submission (C++) : N/A

[CCC 2005 Day1]

Background

한필이가 매트릭스에 갇혀있다.: 아니.. 행렬 말고, 영화처럼 그런 매트릭스(matrix)에 갇혀있다.(영화 큐브와 비슷) 매트릭스는 가로 방향으로 N(1<= N <=100) 개의 칸으로 구성되고, 세로 방향으로 M(1<= M <=100)개의 줄로 구성되어있는 크기이고 각 칸에는 0~9 중 하나의 정수가 들어있다.

한필이는 맨 처음에 첫 줄에서 어떤 위치를 임의로 선택할 수 있고, 그 이후에 M번째 줄까지 이동해야만 그 매트릭스를 탈출할 수 있다.

하지만 한 가지 제약사항이 있는데, 맨 처음에 0~9까지의 정수들 중에서 3개를 선택할 수만 있고, 선택한 3가지 수가 적혀있는 곳으로만 이동할 수 있다,

이동하는 경로는 첫 번째 줄에서 어떤 위치에서 시작해서 왼쪽, 오른쪽, 위, 아래(대각선으로는 이동할 수 없다.) 방향으로 가능하고, 선택한 3가지 수들로만 이동이 가능하다.

3개의 수를 잘 못 선택하면, 한필이는 영원이 매트릭스에 갇혀 빠져나오지 못한다.

한필이가 매트릭스를 탈출하기 위해 선택해야하는 3개의 수를 찾아 출력해보자. 여러 가지 경우가 가능한 경우에는 오름차순으로 가장 빠른 것으로 출력한다. 0 1 2 이 0 2 3 보다 빠르다.
(오름차순으로 정리해 출력해야 한다.)

만약 어떻게라도 탈출하지 못한다면 3개의 –1을 출력한다. 만약, 숫자 1개로 된다면 1 1 1 과 같은 형태로 출력하고, 2개로 된다면, 1 1 2와 같이 출력해야 한다.

Input

첫 줄에 N, M이 공백을 두고 입력된다.

다음 M개의 줄에는 N개의 수가 공백을 두고 차례대로 입력된다.

Output

3개의 수를 한 줄로 출력한다.

IO Example

입력
6 5
0 1 2 3 4 5
0 0 0 1 1 1
0 1 2 3 3 4
5 1 4 1 9 4
9 5 6 2 4 6

출력
0 1 5

설명 : 0 1 5를 3개 선택하면 첫줄에서 마지막 줄까지 3가지 중 한 숫자를 선택하면서 매트릭스를 빠져나갈 수 있다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]