PRoblem

Codejamon 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 × D square of grid cells (with D ≥ 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. Input

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 Ri and Ci, 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.) Output

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 the total number of safe zones for this test case. Limits

1 ≤ T ≤ 20.

(Ri, Ci) ≠ (Rj, Cj) for i ≠ j. (No two monsters are in the same grid cell.)

0 ≤ Ri < R, i from 1 to K

0 ≤ Ci < C, i from 1 to K

Small dataset

1 ≤ R ≤ 10.

1 ≤ C ≤ 10.

0 ≤ K ≤ 10.

Large dataset

1 ≤ R ≤ 3000.

1 ≤ C ≤ 3000.

0 ≤ K ≤ 3000.

分析：

然而，當(dāng)矩陣[i-1][j-1]位置無monster，即為安全的時候，就要考慮更多了：因為由于[i-1][j-1]位置是安全的，導(dǎo)致產(chǎn)生了新的safe square。這時候我用另外的兩個矩陣來存儲了需要的信息，即square[R+1][C+1]及stretch[R+1][C+1]。

這兩個矩陣可以幫助計算[i-1][j-1]位置的加入而新產(chǎn)生的safe square個數(shù)，即為

這里我的方法開了很多數(shù)組，占用了不少空間?？隙ㄟ€有更好的方法解決這個問題。

代碼：Github