"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.
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'.
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.
4 5 6 2 4 5 6 4 1 2 2 4 5 6 1 3 3 6 5 6 5 3 3
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.
For all subtasks, 1 ≤ R ≤ 1,000, 1 ≤ C ≤ 100,000 and 1 ≤ K ≤ 1,000,000.