Canadian Computing Olympiad: 2016 Day 2, Problem 2
Your country has a problem with zombies. That is, it has zombies, which are a problem. Thankfully, you are gainfully employed at the Forensic Institute for Zoology and Zombie Emerging Studies (FIZZES), and your job is simply to give a measure of how bad the problem is.
You have mapped out your country on an -by-
array of cells marked with non-negative integers.
You have the exact locations of all the zombies, and know that no two zombies are in the same location. The cells containing a zombie are marked with 0
. Next, all the unmarked cells touching a cell (where touching a cell means touching on any side or corner of a cell; so each cell touches up to other cells) marked with
0
are marked with 1
. Then, all the unmarked cells touching a cell marked with 1
are marked with 2
. This process continues until all the cells are marked. These numbers indicate the level of concern your office has about the spread of zombies.
A small example is shown below.
2 2 1 1 1 2
2 1 1 0 1 2
2 1 0 1 1 2
2 1 1 1 2 2
2 2 2 2 2 3
Your boss has given you an integer , and you must determine the number of cells which are marked with the integer
.
Input Specification
The first line of input will contain two space-separated integers and
indicating the size of the grid. The next line will contain the number
, indicating the number of cells that contain zombies. The next
lines each contain two space separated integers
indicating the row and column of the
th zombie
. No two zombies are in the same cell: thus if
then
. The last line will contain the integer
.
For of the
marks available,
and
.
For an additional of the
marks available,
.
For an additional of the
marks available,
.
Output Specification
Output the number of cells in the grid that are marked with the integer .
Sample Input
5 6
2
3 3
2 4
2
Sample Output
15
Explanation
The sample input is the example shown above, which has
2
's.
Comments