AOJ 0515 School Road

碁盤の目の左上から右下まで進む全事象の数を求める．ただし工事中のポイントがいくつかあってそこは通れない．

やりかた：左上に近いポイントから「ここまでの進み方は何通りあるか」を順番に右下まで計算する←動的計画法！

以下図解．

1--0--0--0--0 4行5列の例
|  |  |  |  | スタート地点を1にしておく
0--X--0--X--0 Xのところは工事中で通れない
|  |  |  |  | （チェック用配列で先にチェックしておく）
0--X--0--0--0
|  |  |  |  |
0--0--0--0--0


1--1
|  | ←1通り
1--? ←←←この?までの行き方は，
 ↑1通り  ?の上の地点に行く全事象の数と
        ?の左の地点に行く全事象の数を足したもの→2通り
        (→↓と↓→)

お分かりいただけるだろうか
1--1--1--1--1
|  |  |  |  |
1--X--1--X--1
|  |  |  |  |
1--X--1--1--2
|  |  |  |  |
1--1--2--3--5

実際にやるときは上と左に番兵を置いとく（与えられた行数と列数より1つずつ増やして，[1][1]からスタートする）と境界チェックが楽．

import std.stdio;
import std.algorithm;
import std.math;
import std.string;
import std.conv;
import std.range;

void main() {
    while (true) {
        int c, r;
        readf("%d %d\n", &c, &r);
        if (r == 0 && c == 0) break;

        // 0行目と0列目を番兵にする
        int[][] map = new int[][](r + 1, c + 1);
        map[1][1] = 1;
        bool[][] bad = new bool[][](r + 1, c + 1);
        int n = readln.chomp.to!int;
        foreach (i; 0..n) {
            int x, y;
            readf("%d %d\n", &x, &y);
            bad[y][x] = true;
        }

        int[][] q = [[2,1], [1,2]];
        while (!q.empty) {
            int[] p = q.front;
            q.popFront;
            int y = p[0], x = p[1];
            // 工事中なら飛ばす
            if (bad[y][x])
                continue;
            // 左と上の足し算が今いるポイントまで行く事象数
            map[y][x] = map[y-1][x] + map[y][x-1];
            // badをチェック済み配列としても使う
            bad[y][x] = true;
            // 右と下をキューに追加
            if (y + 1 <= r) q ~= [y+1, x];
            if (x + 1 <= c) q ~= [y, x+1];
        }

        map[r][c].writeln;
    }
}

AOJ - Problem 0515 : School Road - ひよっこプログラマのプログラミングを見ると工事中のポイントは上で言うmapに-1をセットしてたりキューを使わずにforループで処理しててなるほどと思った．キューの使い方を覚えたからと言ってやたらめったら使ってしまって良くない．