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

"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 line of input will contain one line with three space-separated
integers R C K, respectively representing the number of rows and columns in the grid, and the number of different colours of blocks.
- The following R lines of input will each contain C space-separated integers representing the colour of the blocks in the current row from left to right. Each of these C integers will be between 1 and K inclusive.

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

2

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.

- For Subtask 1 (20 points), 1 ≤ K ≤ 10 and C ≤ 1,000.
- For Subtask 2 (30 points), R = 1.
- For Subtask 3 (30 points), 1 ≤ K ≤ 1,000 and C ≤ 1,000.
- For Subtask 4 (20 points), C ≤ 1,000.

Privacy
statement

© Australian Mathematics Trust 2001-2021

Page generated: 1 December 2021, 11:55am AEDT