AIOC Banner

Problem: Janitor

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


Janitor

Input File: janitorin.txt
Output File: janitorout.txt
Time Limit: 1 second
Memory Limit: 1 GB

Congratulations! You have been appointed head bathroom janitor of your school! Okay, okay, I know you're not thrilled, but somebody has to do it. We thank you for your sacrifice.

The bathroom floor is covered in a rectangular grid of tiles. No one is watching you very closely, so pouring a bucket of water over the floor is enough to make it look like you cleaned it. There is one small problem. The floor is uneven, so depending on which tile you pour the water on, some tiles may not become wet at all, and your deception will be exposed.

Water can flow from any square to any adjacent square of lower height, where adjacent squares may be to the north, south, east or west (water cannot flow across diagonals).

To finish your chore as soon as possible, you've decided to find out what is the fewest number of tiles you need to pour water on to make sure every tile becomes wet.

To complicate matters further, the bathroom is undergoing some hasty renovations. Each day, a tradie will replace one of the tiles, changing its height. After each replacement, you will need to figure out again how many tiles you need to pour water on.

Input

Output

The output should contain Q+1 lines. The first line should contain the fewest tiles you need to pour water on to make sure every tile gets wet before any replacements are made. The next Q lines should correspond to the Q tile replacements. After each replacement has been made (including all previous modifications), your program should write one line containing the fewest tiles you need to pour water on to make sure every tile gets wet.

Sample Input

3 4 3
5 3 2 0
4 8 4 3
5 7 6 1
2 3 1
3 1 2
2 3 9

Sample Output

2
3
3
2

Explanation




Initially, you need to pour water on the tile of height 5 and the tile of height 8. From there, the water will spread to the rest of the tiles. You can't cover the entire floor by pouring on one tile, so the answer is 2.

After the first replacement, you need to additionally pour water on the tile in the 2nd row, 4th column (which has height 3). Now the answer is 3.

After the second replacement, pouring on the same three tiles is still the best you can do.

After the last replacement, you can cover the floor by pouring on the height 5 tile and the newly added height 9 tile. The answer is 2 again.

Subtasks & Constraints

For all subtasks:

Subtasks:

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 26 August 2019,  4:20am AEST