DP の典型問題だけど、最初は難しく感じるかもしれない。あと、縦横が微妙に混乱するね。

問題概要 (今風に表現改)

$H \times W$ のグリッドが与えられる。このグリッドで上から $i$ 番目、左から $j$ 番目のマスを $(i, j)$ と書くことにする。最初、マス $(1, 1)$ に駒があって、駒をマス $(H, W)$ へと運びたい。駒は右方向または下方向にのみ動かすことができる。

ただし、マスのうち $N$ 個のマスには駒を動かすことができない。

駒をマス $(1, 1)$ から $(H, W)$ へと動かす経路の本数を求めよ。

制約

$1 \le H, W \le 16$
$1 \le N \le 40$

最初に注意：縦と横

まず、この時代の JOI は、今の ABC などと比べると二次元グリッドの「縦」「横」の仕様が違っていてややこしい。ここでは、今風の「縦」「横」に改めて考えることにする。そうすると、上のような問題文になる。

入力例 1 で様子を見る

図示すると、下図のようになる。左上のマス S から右下のマス G へと至る経路の本数を求めたい。

いきなり、ゴールを考えるのは大変なので、左上から順に考えることにしよう。まず、上から 1 行目の各マスについて、スタートからの経路数を数えると下図のようになる。駒は右か下にしか行けないので、どのマスも「スタートから右へまっすぐ進む」ことでしか到達できないためだ。

同様に、2 行目、3 行目の各マスに対しても、スタートからそのマスへ至る経路の本数を求めると、下図のようになる。ここで、たとえばマス (3, 4) は、

上のマス (2, 4) から来る方法
左のマス (3, 3) から来る方法

とがあるので、合わせて 2 通りとなる。

さらに 4 行目も求めると、下図のようになる。ここで、マス (4, 4) は、

上のマス (3, 4) から来る方法が 2 通り
左のマス (4, 3) から来る方法が 1 通り

があるので、合わせて 2 + 1 = 3 通りとなる。

この調子で最後の 5 行目も求めると、下図のようになる。結局ゴールのマス (5, 4) へと至る経路の本数は 5 本であると求められた。

一般化

ここまでの手続きを一般化して考えよう。まず、次の 2 次元配列 dp を用意する。

dp[i][j] ← スタートマスから、マス $(i, j)$ へと至る経路の本数

さて、スタートマスから、マス $(i, j)$ へと至る経路は大きく分けて 2 つに分けられる。

上のマス $(i-1, j)$ を経由して来る経路
左のマス $(i, j-1)$ を経由して来る経路

1 は dp[i-1][j] 通り、2 は dp[i][j-1] 通りなので、結局

dp[i][j] = dp[i-1][j] + dp[i][j-1]

と書けることがわかった。この式に従って、各マス $(i, j)$ の値を順に求めていけばよい。

以上の処理は下のコード例のように実装できる。計算量は $O(HW)$ となる。

コード

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

int main() {
    // 入力
    int H, W, N;
    cin >> H >> W >> N;
    
    // NG
    vector<vector<bool>> is_ok(H+1, vector<bool>(W+1, true));
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        is_ok[a][b] = false;
    }
    
    // DP
    vector<vector<long long>> dp(H+1, vector<long long>(W+1, 0));
    dp[1][1] = 1;  // 初期状態は (1, 1);
    
    // DP ループ
    for (int h = 1; h <= H; ++h) {
        for (int w = 1; w <= W; ++w) {
            // NG 交差点の場合はスキップ
            if (!is_ok[h][w]) continue;
            
            // 上から来る場合
            dp[h][w] += dp[h - 1][w];
            
            // 左から来る場合
            dp[h][w] += dp[h][w - 1];
        }
    }
    cout << dp[H][W] << endl;
}