Consider solving this problem with DP (Dynamic Programming). Define

• \(\mathrm{dp}[i][j] :=\) (the maximum side \(n\) of a holeless square whose bottom-right corner is \((i, j)\), or \(0\) if no such square exists).

(If \((i, j)\) is out of the range \(1 \leq i \leq H\) and \(1 \leq j \leq W\), then let \(\mathrm{dp}[i][j] = 0\).)

Then the answer to this problem is expressed using \(\mathrm{dp}[i][j]\) as:

\[\sum_{i=1}^H \sum_{j=1}^W \mathrm{dp}[i][j].\]

(Proof) Every holeless square has a unique bottom-right square. Also, if \(\mathrm{dp}[i][j] = k\), then the square of size \(n\) whose bottom-right square is \((i,j)\) is a holeless square for all \(n=1, 2, \dots, k\). Thus, every holeless squares are counted exactly once in the summation above. (End of proof)

• Roughly speaking, you can come up with the expression above as follows:
  • We want to count all the holeless squares.
  • This can be solved if we can count the number of holeless squares whose bottom-right square is \((i, j)\) for all squares \((i, j)\).
  • Let’s solve the subproblem with DP!

So, the problem can be solved if \(\mathrm{dp}[i][j]\) is found for all \(1 \leq i \leq H\) and \(1 \leq j \leq W\).

With some observations, we obtain the following recurrence relations on \(\mathrm{dp}[\ast][\ast]\) as follows:

\[ \mathrm{dp}[i][j] = \begin{cases} \min\lbrace \mathrm{dp}[i-1][j], \mathrm{dp}[i][j-1], \mathrm{dp}[i-1][j-1] \rbrace + 1 & S[i][j] = \mathrm{o}\\ 0 & S[i][j] = \mathrm{x} \end{cases} \]

This is justified because, for all squares \((i, j)\) and positive integers \(n\), “1.” if and only if “2., 3., 4., and 5.”. (You may understand it by drawing a figure.)

1. A square region of size \(n\) whose bottom-right square is \((i, j)\) is holeless.
2. A square region of size \((n-1)\) whose bottom-right square is \((i, j-1)\) is holeless.
3. A square region of size \((n-1)\) whose bottom-right square is \((i-1, j)\) is holeless.
4. A square region of size \((n-1)\) whose bottom-right square is \((i-1, j)\) is holeless.
5. \((i, j)\) is not holed.

Thus, it is sufficient to compute \(\mathrm{dp}[i][j]\) \((1 \leq i \leq H, 1 \leq j \leq W)\) in ascending order of \(i\), then in \(j\).
The complexity is \(\mathrm{O}(HW + N)\), which is fast enough.

• Sample code (C++)

#include <bits/stdc++.h>
using namespace std;

constexpr int nmax = 3030;
int hole[nmax][nmax];
int dp[nmax][nmax];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int H, W, N;
  cin >> H >> W >> N;
  for (int i = 0, a, b; i < N; i++) {
    cin >> a >> b, hole[a][b] = 1;
  }
  long long ans = 0;
  for (int i = 1; i <= H; i++) {
    for (int j = 1; j <= W; j++) {
      if (hole[i][j]) continue;
      dp[i][j] = min({dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]}) + 1;
      ans += dp[i][j];
    }
  }
  cout << ans << "\n";
}