CCO '16 P5 - Zombie Apocalypse

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem types
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 N-by-M 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 8 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 Q, and you must determine the number of cells which are marked with the integer Q.

Input Specification

The first line of input will contain two space-separated integers N and M (1 \le N \le 10^9; 1 \le M \le 10^9) indicating the size of the grid. The next line contains the number K (1 \le K \le 2000), indicating the number of cells that contain zombies. The next K lines each contain two space separated integers r_i c_i indicating the row and column of the ith zombie (1 \le r_i \le N; 1 \le c_i \le M). No two zombies are in the same cell: thus if i \neq j then (r_i, c_i) \neq (r_j, c_j). The last line will contain the integer Q (0 \le Q \le N + M).

For 5 of the 25 marks available, N \le 1000 and M \le 1000.

For an additional 5 of the 25 marks available, K \le 50.

For an additional 5 of the 25 marks available, N \le 1000.

Output Specification

Output the number of cells in the grid that are marked with the integer Q.

Sample Input

5 6
2
3 3
2 4
2

Sample Output

15

Explanation

The sample input is the example shown above, which has 15 2's.


Comments


  • 0
    Jeffmagma  commented on Nov. 25, 2017, 9:08 p.m.

    Where's the grammar mistake?