JDCC '15 Contest 1 P5 - Estuary

View as PDF

Submit solution

Points: 12
Time limit: 3.0s
Memory limit: 64M

Problem type

After selling a certain popular sandbox game, Markus has built a landscape of cubes in his backyard and he now wants to run a river across it. His backyard is made up of R rows and C columns, with each location having an integer elevation. Markus wants his river to start at (1, 1) and end at (R, C) and he will continue to raise the water level until this goal is reached. The river's water level will always be an integer and the river will only flow into a block adjacent (up, down, left, right) to it whose elevation is less than the current water level. If any block meets this requirement, the river must flow into it. The river will not flow outside the bounds of the backyard and cannot flow out of the end point. Given these criteria and the elevation of each point in his backyard, find out what the volume of the river will be (the volume of the river at a point is the difference between the water level and the elevation) when his river is finished.

Input Specification

The first line of the input provides the number of test cases, T (1 \le T \le 100). T test cases follow. Each test case begins with a line containing two values, R and C (1 \le R, C
\le 150). R lines follow, each with C space-separated integers, the i^{th} integer being the elevation of the location (R,i). The elevation of a location will at most be 1 000 000.

Output Specification

For each test case, your program should output one integer, the total volume of the river modulo 10^9 + 7.

Sample Input

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

Sample Output



There are no comments at the moment.