通学路には

誰も知らない秘密なんたらかんたら。誰の歌だっけ？

JOI 2006-2007 予選　問題6


いかにも高校生らしい問題ですねコレ。昔は無理やり数えてテストで回答したことがありました（笑）

相変わらず自分の中に無理矢理さは残っているようです

ソース短いので載せときます

#include <iostream>

int point[17][17];
int a, b, m, n;

void calc(int x=1, int y=1)
{
    if (x == a && y == b) {
        m++;
        return;
    }
    if (point[y][x+1] != 1 && x+1 <= a)
        calc(x+1, y);
    if (point[y+1][x] != 1 && y+1 <= b)
        calc(x, y+1);
}

int main()
{
    int x, y;

    cin >> a >> b;
    cin >> n;
    for (int i=0;i < n;i++) {
        cin >> x >> y;
        point[y][x] = 1;
    }
    calc();
    cout << m << endl;

    return 0;
}



とりあえず、いちばんわかりやすい方法でしょうね。強引に解くってのは。

縦横それぞれ最大16ってのと、入力ファイルが上手い具合に作られてるので5番目の入力ファイルでも時間はほとんどかかりません。

intとかlongの上限が42億程度（unsigned指定）なので、それほど計算量がかかる経路は作れないはず

まぁ、スマートな方法とは言えません。再帰はすっきり書けるけどね

解説の方では

・二重forループ（DPっぽい）

・再帰

・全数調査

の3つが挙げられてますね。DPのやってみようかしら