아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

숫자 행렬

시간 제한2초메모리 제한512 MB

요약
숫자 격자가 주어질 때, 1행에서 M행까지 이동하는 경로가 사용하는 칸의 숫자가 모두 포함되도록 하는 세 자릿수의 집합 중 사전순으로 가장 작은 것을 찾는다.
난이도

보통10점 중 6점

유형
그래프, BFS, 완전 탐색, 행렬
정답자
아직 제출이 없습니다

문제

조니는 숫자로 이루어진 행렬에 갇혔다. 행렬은 MM개의 행(1≤M≤1001 \le M \le 100)과 NN개의 열(1≤N≤1001 \le N \le 100)로 이루어진 격자이며, 각 칸에는 00부터 99까지의 한 자리 숫자가 하나씩 들어 있다.

조니는 첫 번째 행의 아무 칸에서나 출발할 수 있으며, 탈출하려면 마지막 행(제 MM행)의 어떤 칸에든 도달해야 한다. 한 번에 상하좌우 중 한 방향으로 한 칸씩 이동하며, 대각선 이동은 할 수 없다.

이동을 시작하기 전에 조니는 00부터 99까지의 숫자 중 정확히 세 개(삼중 숫자)를 고른다. 세 숫자는 서로 같아도 된다. 조니는 자신이 고른 세 숫자 중 하나가 적힌 칸에만 설 수 있으며, 이는 출발 칸에도 적용된다. 첫 행의 출발 칸부터 마지막 행의 도착 칸까지 경로에 포함된 모든 칸의 숫자는 고른 세 숫자 중 하나여야 한다.

조니가 어떤 세 숫자를 골라야 하는지 구하여라.

입력

첫째 줄에 두 정수 NN과 MM이 주어진다.

다음 MM개의 줄에는 각각 격자의 한 행을 나타내는 NN개의 숫자가 공백으로 구분되어 주어진다.

출력

조니가 탈출하기 위해 골라야 하는 세 숫자를 공백으로 구분하여 한 줄에 출력한다.

가능한 세 숫자 조합이 하나 이상 있으면, 세 숫자를 순서 있는 삼중값으로 비교했을 때 사전순으로 가장 앞서는 것을 출력한다. 즉 0 0 0이 0 0 1보다 앞서고, 0 0 1이 0 0 2보다 앞서며, ..., 9 9 8이 9 9 9보다 앞선다. 세 숫자는 서로 같아도 된다.

어떤 세 숫자를 골라도 마지막 행에 도달할 수 없으면 -1 -1 -1을 출력한다.

예제1

  1. 예제 1

    입력
    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