3195 发现宝藏
题目描述 Description
小毛在一块地方发现了一块宝藏，他把这块地方看成为一个a*b的矩阵，有a条南北方向的道路和b条东西方向的道路。南北方向的a条道路从西到东依次编号为l到a，而东西方向的b条道路从南到北依次编号为l到b，南北方向的道路i和东西方向的道路j的交点记为(i，j)。小毛现在在(1，1)入口处，而宝藏点在(a，b)处，他只能沿着道路走，而且为了缩短时间只允许沿着向东和北的方向行驶。现在有n个交叉路口(X1，Yl)、(X2，Y2)……，(Xn，Yn)，有大块石头挡路，这些路口是不能行走的，请你帮小毛统计一共有多少种走法到达宝藏点?
输入描述 Input Description
第一行包含两个整数a和b(1≤a，b≤16)；第二行包含一个正整数n(1≤n≤40)，表示有n个路口有大块石头挡路；接下来n行，每行两个整数Xi,Yi，描述路口的位置，以空格隔开。
输出描述 Output Description
输出一个整数表示从(1，1)到(a，b)的行走路线总方法数。
样例输入 Sample Input
5 4
3
2 2
2 3
4 2
样例输出 Sample Output
5
题解
因为只能向右走或向下走，所以从（1,1）到（i，j）的路径条数只与到达（i-1,j）和（i，j-1）的路径条数有关，
所以转移方程为f[i][j]=f[i-1][j]+f[i][j-1]。
#include<cstdio>
using namespace std;
int f[20][20],a,b,n;
bool c[20][20];
int main()
{
int i,j,x,y;
scanf("%d%d%d",&a,&b,&n);
for(i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
c[x][y]=1;
}
f[1][1]=1;
for(i=1;i<=a;i++)
for(j=1;j<=b;j++)
if(!f[i][j]&&!c[i][j])
f[i][j]=f[i][j-1]+f[i-1][j];
printf("%d",f[a][b]);
}