## CCO '05 P1 - Number Matrix

View as PDF

Points: 10
Time limit: 2.0s
Memory limit: 64M

Problem types
##### Canadian Computing Competition: 2005 Stage 2, Day 1, Problem 1

Johnny Cannook has been trapped in the matrix: no, not that matrix. This matrix is a grid of width numbers (in the range to ) in each row, and rows .

Johnny can pick any position on the first row to begin at. He must make it to row of the matrix in order to escape.

However, there is a restriction. Johnny can only choose a trinity of numbers (from the range to ), and he can only step on those positions which are one of these three chosen numbers. That is just the way it is.

The path may begin at any position in row , and can move left, right, up, or down (no diagonal movement allowed) to any number, so long as that number is in the set of the chosen three.

#### Input Specification

The first line of input contains the two integers and . On the next lines, there are numbers (each separated by a space).

#### Output Specification

The output is one line long, containing three integers: the trinity of numbers that Johnny should chose in order to escape the matrix. If there is no path from row to row (that is, Johnny is stuck in the matrix FOREVER), the output should be three -1. If there is a path, then the lexicographically first three numbers should be outputted. (Notice that , , comes before , , , which comes before , , , , which comes before , , which comes before , , ). You should notice that the three chosen numbers need not be distinct.

#### Sample Input

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

#### Sample Output

0 1 5