P16585 [GKS 2016 #C] Safe Squares

Codejammon trainers are actively looking for monsters, but if you are not a trainer, these monsters could be really dangerous for you. You might want to find safe places that do not have any monsters! Consider our world as a grid, and some of the cells have been occupied by monsters. We define a **safe square** as a grid-aligned $D \times D$ square of grid cells (with $D \ge 1$) that does not contain any monsters. Your task is to find out how many safe squares (of any size) we have in the entire world.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case starts with a line with three integers, $R$, $C$, and $K$. The grid has $R$ rows and $C$ columns, and contains $K$ monsters. $K$ more lines follow; each contains two integers $R_i$ and $C_i$, indicating the row and column that the i-th monster is in. (Rows are numbered from top to bottom, starting from 0; columns are numbered from left to right, starting from 0.)

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the total number of safe zones for this test case.

The grid of sample case #1 is: ``` 0 0 0 0 0 0 0 1 0 ``` Here, 0 represents a cell with no monster, and 1 represents a cell with a monster. It has $10$ safe squares: $8$ $1\times 1$ and $2$ $2\times 2$. The grid of sample case #2 is: ``` 0 1 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 ``` Note that sample case #2 will only appear in the Large dataset. It has $51$ safe squares: $32$ $1\times 1$, $13$ $2\times 2$, $5$ $3\times 3$, and $1$ $4\times 4$. ### Limits $1 \le T \le 20$. $(R_i, C_i) \ne (R_j, C_j)$ for $i \ne j$. (No two monsters are in the same grid cell.) $0 \le R_i < R$, i from $1$ to $K$ $0 \le C_i < C$, i from $1$ to $K$ **Small dataset (Test set 1 - Visible)** $1 \le R \le 10$. $1 \le C \le 10$. $0 \le K \le 10$. **Large dataset (Test set 2 - Hidden)** $1 \le R \le 3000$. $1 \le C \le 3000$. $0 \le K \le 3000$.