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~.
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 ~i~th zombie ~(1 \le r_i \le N; 1 \le c_i \le M)~. No two zombies are in the same cell: thus if ~i \ne j~ then ~(r_i, c_i) \ne (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 the number of cells in the grid that are marked with the integer ~Q~.
5 6 2 3 3 2 4 2
The sample input is the example shown above, which has ~15~