2005 Canadian Computing Competition, Stage 2

Day 1, Problem 1: Number Matrix

Johnny Cannook has been trapped in the matrix: no, not that matrix. This matrix is a grid of width N (1 ≤ N ≤ 100) numbers (in the range 0 to 9) in each row, and M rows (1 ≤ M ≤ 100). Johnny can pick any position on the first row to begin at. He must make it to row M of the matrix in order to escape.

However, there is a restriction. Johnny can only choose a trinity of numbers (from the range 0 to 9), 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 1, 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

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

Output

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 1 to row M (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 0, 0, 0 comes before 0, 0, 1, which comes before 0, 0, 2, ..., which comes before 9, 9, 8 which comes before 9, 9, 9). 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

All Submissions
Best Solutions


Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Dec 23, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Test case #10 does not conform to the input constraint that the matrix only has numbers in the range from 0 to 9. The number 10 appears in the matrix in that test case.

Irrespective of that violation, if you are only allowed to use numbers from 0 to 9, then the test data are correct otherwise.

I only discovered this because I checked if a number was valid by generating a boolean array of size 10, which caused an AIOOBE in Java. If you opt to do something else, like using a set to check membership, this actually shouldn't be a concern.

Test data updated, and submissions are rejudged.

Why do I get a SIGSEGV error for test case 4 afer the test data was updated and my solution was rejudged?

Test case 4 was not altered. Your submissions have undefined behaviour, getting SIGSEGV about half the time when I rejudge them, and AC other times.