通学路には
誰も知らない秘密なんたらかんたら。誰の歌だっけ?
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のやってみようかしら