Unflood The World
Statement
Goal
A rectangular map is made of squares, each with a specific height.When it rains, the water falls evenly on all squares.
The water flows down from any square to an adjacent lower one. The water also flows freely between adjacent squares of equal height. If a square is surrounded by higher squares, the water just accumulates there.
You are allowed to build drains in some squares.
When a square has a drain, all the water that would accumulate on it will leak out instead.
What is the minimum number of drains that have to be built to leak out all the rain water?
NOTE: Adjacency is horizontal or vertical. Squares that touch diagonally through a corner aren't adjacent.
NOTE: The water can never flow outside the map. You can consider it bounded by walls of infinite height.
Input
First line: integers N and M - width and height of map
Next M lines: N space separated integers between 1 and 10000 - height of each square
Next M lines: N space separated integers between 1 and 10000 - height of each square
Output
A single integer - number of drains to be built.
Constraints
1 <= N, M <= 100
Example
Input
5 4 5 5 5 5 5 5 4 4 4 5 5 3 2 1 5 5 5 5 5 5
Output
1
Tags
Difficulty
Test cases
One drain Test
Input
5 4
5 5 5 5 5
5 4 4 4 5
5 3 2 1 5
5 5 5 5 5
Output
1
One drain 2 Validator
Input
4 5
5 5 5 5
5 4 4 5
5 3 2 5
5 4 1 5
5 5 5 5
Output
1
Hill Test
Input
7 5
1 1 1 1 1 1 1
1 2 2 2 2 2 1
1 2 3 9 3 2 1
1 2 2 2 2 2 1
1 1 1 1 1 1 1
Output
1
Hill 2 Validator
Input
5 7
1 1 1 1 1
1 2 2 2 1
1 2 3 9 1
1 2 2 2 1
1 2 2 2 1
1 2 2 2 1
1 1 1 1 1
Output
1
Wall Test
Input
5 3
1 1 9 1 1
1 1 9 1 1
1 1 9 1 1
Output
2
Wall 2 Validator
Input
5 3
2 3 4 5 6
9 9 9 9 9
5 4 3 2 1
Output
2
Flat field Test
Input
3 3
1 1 1
1 1 1
1 1 1
Output
1
Flat field 2 Validator
Input
1 1
10000
Output
1
Chess board Test
Input
5 5
1 2 1 2 1
2 1 2 1 2
1 2 1 2 1
2 1 2 1 2
1 2 1 2 1
Output
13
Chess board 2 Validator
Input
5 4
1 11 2 12 3
13 4 14 5 15
6 16 7 17 8
18 9 19 10 20
Output
10
Fractal Test
Input
9 9
2 2 2 2 2 2 2 2 2
2 1 2 2 1 2 2 1 2
2 2 2 2 2 2 2 2 2
2 2 2 1 1 1 2 2 2
2 1 2 1 1 1 2 1 2
2 2 2 1 1 1 2 2 2
2 2 2 2 2 2 2 2 2
2 1 2 2 1 2 2 1 2
2 2 2 2 2 2 2 2 2
Output
9
Walls 3 Validator
Input
5 4
1 9 9 1 1
9 1 2 9 2
9 4 3 9 1
9 8 7 6 2
Output
4
Maze Test
Input
9 9
1 2 3 4 5 6 7 8 9
999 999 999 999 999 999 999 999 10
31 32 33 34 35 36 37 999 11
30 999 999 999 999 999 38 999 12
29 999 47 48 49 999 39 999 13
28 999 46 999 999 999 40 999 14
27 999 45 44 43 42 41 999 15
26 999 999 999 999 999 999 999 16
25 24 23 22 21 20 19 18 17
Output
1
Maze 2 Validator
Input
7 5
2 9 2 9 1 9 2
2 3 2 9 2 3 2
9 2 9 9 9 2 9
9 2 2 2 2 2 9
9 9 9 1 9 9 9
Output
5
Plateaus Test
Input
6 6
1 1 2 2 3 3
1 1 2 2 3 3
6 6 5 5 4 4
6 6 5 5 4 4
7 7 8 8 9 9
7 7 8 8 9 9
Output
1
Plateaus 2 Validator
Input
6 6
1 1 6 6 7 7
1 1 6 6 7 7
2 2 5 5 8 8
2 2 5 5 8 8
3 3 4 4 9 9
3 3 4 4 9 9
Output
1
Solution language
Solution
Stub generator input