PEG Judge - CCO16 - Zombie Apocalypse

2016 Canadian Computing Olympiad

Day 2, Problem 2 - Zombie Apocalypse

Your country has a problem with zombies. That is, it has zombies, which are a problem. Thankfully, you are gainfully employed at the Forsenic 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 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 Format

The first line of input will contain two space-separated integers N and M (1 ≤ N ≤ 10⁹; 1 ≤ M ≤ 10⁹) indicating the size of the grid. The next line contains the number K (1 ≤ K ≤ 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 i-th zombie (1 ≤ r_i ≤ N; 1 ≤ c_i ≤ M). No two zombies are in the same cell: thus if i ≠ j then (r_i, c_i) ≠ (r_j, c_j). The last line will contain the integer Q (0 ≤ Q ≤ N + M).

For 5 of the 25 marks available, N ≤ 1000 and M ≤ 1000.
For an additional 5 of the 25 marks available, K ≤ 50.
For an additional 5 of the 25 marks available, N ≤ 1000.