AOJ - Problem 0515 : School Road

• 問題文

スタートからゴールまでの経路が何通りあるか調べる問題です。典型的な動的計画法で解くことができます。
動的計画法については最強最速アルゴリズマー養成講座のアルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だったの説明がわかりやすいと思います。

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
	int a,b;
	while( cin >> a >> b , a||b ){
		int n,f[20][20] = {0};
		f[1][1] = 1;

		cin >> n;
		for(int i=0 ; i < n ; i++ ){
			int x,y;
			cin >> x >> y;
			f[y][x] = -1;
		}
		for(int y=1 ; y <= b ; y++ ){
			for(int x=1 ; x <= a ; x++ ){
				if( f[y][x] != -1 ){
					if( y != 1 && f[y-1][x] != -1 ){
						f[y][x] += f[y-1][x];
					}
					if( x != 1 && f[y][x-1] != -1 ){
						f[y][x] += f[y][x-1];
					}
				}
			}
		}
		cout << f[b][a] << endl;
	}
}