$H \times W$ のグリッド上に $N$ 個の「穴（障害物）」が存在する際、穴を一切含まない正方形がいくつ存在するかを計算する問題は、動的計画法（DP）の典型的な応用例です。本記事では、この問題に対する直感的だが誤ったアプローチの分析と、それを修正した最適なアルゴリズムについて解説します。

誤ったアプローチ：独立した連続長に基づく累積和

まず考えられがちな誤解として、2次元累積和を用いる方法があります。この手法では、各マス $(i, j)$ において「上方向に連続する空きマスの数」と「左方向に連続する空きマスの数」の最小値を計算し、それを新たな正方形の数として全体の累積和に加算しようとします。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int rows, cols, holes;
    if (!(cin >> rows >> cols >> holes)) return 0;

    vector<vector<bool>> is_hole(rows + 1, vector<bool>(cols + 1, false));
    for (int k = 0; k < holes; ++k) {
        int r, c;
        cin >> r >> c;
        is_hole[r][c] = true;
    }

    vector<vector<long long>> total_squares(rows + 1, vector<long long>(cols + 1, 0));
    vector<int> up_consecutive(cols + 1, 0);
    vector<int> left_consecutive(rows + 1, 0);

    for (int i = 1; i <= rows; ++i) {
        for (int j = 1; j <= cols; ++j) {
            if (is_hole[i][j]) {
                up_consecutive[j] = 0;
                left_consecutive[i] = 0;
            } else {
                up_consecutive[j]++;
                left_consecutive[i]++;
            }
            long long new_squares = min(up_consecutive[j], left_consecutive[i]);
            total_squares[i][j] = total_squares[i - 1][j] + total_squares[i][j - 1] 
                                  - total_squares[i - 1][j - 1] + new_squares;
        }
    }
    
    cout << total_squares[rows][cols] << endl;
    return 0;
}

論理的な欠陥

上記の実装には重大な論理欠陥があります。以下の $2 \times 2$ グリッドを例に考えてみましょう。

$(1, 1)$ に穴があり、他の3マスは空きです。このコードは $(2, 2)$ の計算において、min(up_consecutive[2], left_consecutive[2]) を評価し、min(2, 2) = 2 となります。これにより、サイズ2の正方形が1つ新たに形成されたと誤認し、結果として総数は4と出力されます。しかし実際には、サイズ1の正方形が3つ存在するだけであるため、正解は3です。

この誤りの原因は、上方向と左方向の連続性しか確認しておらず、対角線上（左上）に穴が存在するケースを考慮できていない点にあります。サイズが2以上の正方形を形成するには、左上のマスも空きである必要があります。

正しいアプローチ：最大正方形の辺の長さを状態とするDP

この問題を正しく解決するためには、DPの状態定義を根本から変更します。dp[i][j] を「右下の頂点が $(i, j)$ となる、穴を含まない最大の正方形の一辺の長さ」と定義します。

右下が $(i, j)$ となる最大の正方形の辺の長さが $L$ であれば、そのマスを右下角とする有効な正方形は、辺の長さが $1, 2, \dots, L$ のちょうど $L$ 個存在することになります。したがって、グリッド全体での有効な正方形の総数は、すべての dp[i][j] の総和となります。

状態遷移は以下のルールに基づきます。マス $(i, j)$ が穴でない場合、そのマスを右下とする最大の正方形は、隣接する3方向（上、左、左上）で作られる最大の正方形のサイズのうち、最も小さいものに制限されます。

dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int grid_h, grid_w, num_holes;
    if (!(cin >> grid_h >> grid_w >> num_holes)) return 0;

    // 穴の位置を記録する2次元配列
    vector<vector<bool>> has_hole(grid_h + 1, vector<bool>(grid_w + 1, false));
    for (int i = 0; i < num_holes; ++i) {
        int r, c;
        cin >> r >> c;
        has_hole[r][c] = true;
    }

    // dpテーブル：右下が(r, c)となる最大正方形の一辺の長さ
    vector<vector<int>> max_side(grid_h + 1, vector<int>(grid_w + 1, 0));
    long long valid_square_count = 0;

    for (int r = 1; r <= grid_h; ++r) {
        for (int c = 1; c <= grid_w; ++c) {
            if (has_hole[r][c]) {
                continue; // 穴があるマスは正方形の右下角になれない
            }
            
            // 上、左、左上の最小値に1を加算して現在の最大辺長を求める
            max_side[r][c] = min({max_side[r - 1][c], 
                                  max_side[r][c - 1], 
                                  max_side[r - 1][c - 1]}) + 1;
                                  
            // そのマスに存在する有効な正方形の数を総和に加算
            valid_square_count += max_side[r][c];
        }
    }

    cout << valid_square_count << "\n";
    return 0;
}