AOJ 0515: School Road

DPの基本的な問題。メモ化再帰でも、普通の再帰でも、全探索でも解けるらしい。
ある点に行くのに、左か下から行かなければならないというだけ。

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

int dp[16][16];

int main(){
	int a,b,n;
	while(cin>>a>>b,a||b){
		cin>>n;
		memset(dp,-1,sizeof(dp));
		for(int i = 0; i < n; i++){
			int x,y;
			cin>>x>>y;
			dp[x-1][y-1] = 0;
		}

		dp[0][0] = 1;
		for(int i = 1; i < a; i++){
			if(dp[i][0]){
				dp[i][0] = dp[i-1][0];
			}
		}
		for(int i = 1; i < b; i++){
			if(dp[0][i]){
				dp[0][i] = dp[0][i-1];
			}
		}

		for(int i = 1; i < a; i++){
			for(int j = 1; j < b; j++){
				if(dp[i][j]){
					dp[i][j] = dp[i][j-1]+dp[i-1][j];
				}
			}
		}

		cout<<dp[a-1][b-1]<<endl;
	}
	return 0;
}