動的計画法でこの問題を解くことを考えます。

• \(\mathrm{dp}[i][j] :=\) (マス \((i, j)\) を右下とする穴のない正方形のうち、一辺の長さ \(n\) の最大値。ただし、そのような正方形が存在しない場合は \(0\))

とします。(ただし \((i, j)\) が \(1 \leq i \leq H, 1 \leq j \leq W\) の範囲外である場合は \(\mathrm{dp}[i][j] = 0\))

このとき、この問題の答えは \(\mathrm{dp}[i][j]\) を用いて次の式で表せます。

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

(証明) 全ての穴のない正方形は、どこかのマスをちょうど 1 個だけ右下に持ちます。また、\(\mathrm{dp}[i][j] = k\) であるとき、\(n=1, 2, \dots, k\) 全てについて \((i, j)\) を右下とする縦横 \(n\) の正方形領域は穴のない正方形です。よって、全ての穴のない正方形は上式でちょうど 1 回ずつ数えられます。(証明終わり)

• ラフな説明で言い換えると、次のようなお気持ちを持つと上記の内容にたどり着くことができます。
  • 「全ての穴のない正方形を数える」という問題を解きたい
  • これは「右下が \((i, j)\) である穴のない正方形を数える」という部分問題を全てのマス \((i, j)\) に対して解けば求められる
  • 部分問題を DP で計算しよう！

さて、\(\mathrm{dp}[i][j]\) を \(1 \leq i \leq H, 1 \leq j \leq W\) の範囲で全て計算できればこの問題を解くことができます。

いくらかの観察により、\(\mathrm{dp}[\ast][\ast]\) について次の漸化式が成り立つとわかります。

\[ \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} \]

正当性については、マス \((i, j)\) と正整数 \(n\) に関して、次の 1. と (2. かつ 3. かつ 4. かつ 5.) が同値であることを確認すると示せます。(図を書いてみると式の意味が理解しやすいです。)

1. \((i, j)\) を右下とする一辺の長さが \(n\) の正方形領域に穴が無い。
2. \((i, j-1)\) を右下とする 一辺の長さが \(n-1\) の正方形領域に穴が無い。
3. \((i-1, j)\) を右下とする 一辺の長さが \(n-1\) の正方形領域に穴が無い。
4. \((i-1, j-1)\) を右下とする 一辺の長さが \(n-1\) の正方形領域に穴が無い。
5. \((i, j)\) は穴が無いマスである。

よって、この DP の式に従って \(\mathrm{dp}[i][j]\) \((1 \leq i \leq H, 1 \leq j \leq W)\) を \(i\) 昇順 -> \(j\) 昇順 の順に計算していけばよいです。
計算量は \(\mathrm{O}(HW + N)\) で十分高速です。

• 実装例 (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";
}