题目描述

你所在城市的街道好像一个棋盘，有a条南北方向的街道，和b条东西方向的街道。

南北方向的a条街道从西到东依次编号为1到a，而东西方向的b条街道从南到北依次编号为1到b，南北方向的街道i和东西方向的街道j的交点记为(I,j)。

你住在(1,1)处，而学校在(a,b)处，你骑自行车去上学，自行车只能沿着街道走，而且为了缩短时间只允许沿着向东和北的方向行驶。

现在有N个交叉路口在施工(X1,Y1)、（X2，Y2），，，（Xn,Yn），这些路口是不能通车的。

问你上学一共有多少走法？

输入

第一行包含两个整数a和b,并且满足1<=a,b<=16。

第二行包含一个整数N,表示有N个路口在维修(1<=N<=40)

接下来N行，每行两个整数X_i,Y_i,描述路口的位置。

输出

输出一个整数表示从(1,1)到(a,b)的行车路线总数。

思路

因为是最短路所以只向上向右走就一定是最短路
先把f[1,1]赋值为1，根据 ↑ 可以得出f[i,j]:=f[i-1,j],f[i,j-1]
然后如果是走不了的话就特殊判断不走就可以了
为了防止f[1,1]不被吃掉要加一个 if(i<>0) or (j<>0)

var
  f:array[-10..1000,-10..1000] of longint;
  w:array[-10..1000,-10..1000] of boolean;
  i,j,k,n,m,s,q,p,x,y:longint;
begin
  readln(x,y);
  readln(n);
  for i:=1 to n do
    begin
      readln(q,p);
      w[p,q]:=true;
    end;
  k:=1;
  f[1,1]:=1;
  for i:=1 to y do
    for j:=1 to x do
      begin
        if w[i,j]=true then continue;
        if (i<>1) or (j<>1) then 
        f[i,j]:=f[i-1,j]+f[i,j-1];
      end;
  writeln(f[y,x]);
end.