経路数え上げ の続き。
こんな考え方でもいいはず。
点(x,y)に到達する経路の総数を route(x,y) とする。
点(x,y)に到達するってことは、点(x-1,y)もしくは点(x,y-1)から歩いてくるってことだから、
route(x,y) = route(x-1,y) + route(x,y-1)
さらに: x=0またはy=0ならroute(x,y)=0
点(x,y)が工事中ならroute(x,y)=0
特異点(1,1)ではroute(1,1)=1
だから...
#include <iostream>
#include <utility>
#include <algorithm>
#include <set>
using namespace std;
typedef pair<int,int> point;
// pに至る経路数を求める。 holesは工事中の点群
int route(const point& p, set<point>& holes) {
if ( p == point(1,1) ) return 1; // 出発点
if ( p.first == 0 || p.second == 0 ) return 0; // どっちかが0なら0
if ( holes.find(p) != holes.end() ) return 0; // 工事中なら0
return route(point(p.first-1,p.second),holes)
+ route(point(p.first,p.second-1),holes);
}
int main() {
set<point> holes;
holes.insert(point(2,2)); // あちら
holes.insert(point(2,3)); // こちらで
holes.insert(point(4,2)); // 工事中
cout << route(point(5,4),holes) << endl;
}
実行結果:
5