AIOC Banner

Problem: The Nightlight

Want to try solving this problem? You can submit your code online if you log in or register.


The Nightlight

Input File: standard input
Output File: standard output
Time Limit: 2 seconds
Memory Limit: 512 MB

"Every night I roam the city blocks of Gotham, silently ridding my path of crime, bringing light to a frightened city. Up until now I have been undetected, but there are powerful people who will stop at nothing to extinguish The Nightlight."

On Gotham's R rows by C columns grid of city-blocks, The Nightlight starts in the top-left block and has to finish at the bottom-right block. To retain the element of surprise The Nightlight only moves to adjacent squares either down or to the right. Finding such a path would be easy, but each block has a colour - and she can only move to a block of the same colour as the one she is standing on. Hope is not lost though, she can use her network of spies at any time to change the colour of her block or an adjacent block so that she can move between them - but this takes time - time that Gotham doesn't have.

Your task is to find the minimum total number of times the colour of a block has to be changed in order for The Nightlight to walk to the bottom-right block.

Input

The first of the R lines represents the 'top' line, and the final line represents the 'bottom', similarly the first integer in each of the R lines is the 'left', and the last is the 'right'.

Output

Your program must output a single integer: the minimum total number of times the colour of a block has to be changed in order for The Nightlight to be able to pass from the top-left block to the bottom-right block.

Sample Input

4 5 6
2 4 5 6 4
1 2 2 4 5
6 1 3 3 6
5 6 5 3 3

Sample Output

2

Explanation

\includegraphics{nightlight-sample.eps}

Before moving off the top-left block The Nightlight can change the colour of the block directly beneath her from 1 to 2. This gives her safe passage to that block, and then to the right twice. Then The Nightlight can change the colour of the block she is standing on to 3. This allows The Nightlight to walk to the bottom-right block. This path involved changing the colour of squares twice, so 2 is the answer.

Subtasks & Constraints

For all subtasks, 1 ≤ R ≤ 1,000, 1 ≤ C ≤ 100,000 and 1 ≤ K ≤ 1,000,000.

 


Privacy statement
© Australian Mathematics Trust 2001-2024

Contact: training@orac.amt.edu.au
Page generated: 29 March 2024,  8:46am AEDT