Problem F
Flooding Fields

Farmer John has a problem: it’s raining, and his pastures are at risk of flooding. Luckily he’s invested in a state-of-the-art drain system that ensures that the water level is the same across the farm. He hasn’t been as lucky with the terrain. Farmer John’s cows can only stand on dry land: if the land becomes wet, any cow on that land drowns. Luckily, cows can move one grid sector each hour, giving them a chance to escape the water (the levels of which rise and fall each hour).

Farmer John has divided his field into grid sectors, which he indexes with a row and column. Each grid sector is small enough to only be able to hold one cow.

Given a description of Farmer John’s field, the starting locations of his cows, and the height of the water at each hour, and assuming that Farmer John’s cows are extremely intelligent and prescient, and so can always make the best move, what is the maximum number of Farmer John’s cows that could survive?


There will be a single test case in the input. This test case will begin with a line with three integers, $n$ ($1 \le n \le 100$), $k$ ($0 \le k \le 100$), and $h$ ($1 \le h \le 24$), where $n$ represents the size of Farmer John’s field (it’s $n \times n$ grid sectors), $k$ is the number of cows in the field, and $h$ is the number of hours he needs to track.

Each of the next $n$ lines will contain $n$ integers each, which represent the height of each grid sector of Farmer John’s field ($0 \le \text {height} \le 100$). The first row in the input is row $0$, and the last is row $n-1$. The first column in each row is column $0$, and the last is column $n-1$.

The following $k$ lines will each contain a pair of integers, $r$ followed by $c$ ($0 \le r < n, 0 \le c < n$). Each line indicates the grid sector position of one cow at hour 0, where $r$ is the row and $c$ is the column. No two cows will be in the same position. The next $h$ lines will each contain a single integer, indicating the level of the flood at that hour ($0 \le \text {level} \le 100$). These lines are given in order: hour $1$ first, then hour $2$, and so on. Note that the times start at hour $1$, and the cows’ positions are given at hour $0$, so the cows have an opportunity to move (or MOOOOve) before the first hour’s flood. A grid square is considered to be flooded if its $\text {height} \le \text {level}$ of the flood at a given hour.


Output a single integer denoting the maximum possible number of surviving cows.

Sample Input 1 Sample Output 1
3 1 3
2 1 2
3 1 3
2 4 2
1 1
CPU Time limit 3 seconds
Memory limit 1024 MB
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in