1267 老鼠的旅行 2012年CCC加拿大高中生信息學奧賽

You are a mouse that lives in a cage in a large laboratory.

你是一隻生活在籠子里的實驗室老鼠。

The laboratory is composed of one rectangular grid of square cages, with a total of R rows and C columns of cages (1 ≤ R,C ≤ 25).

實驗室是一個R行C列的格子矩陣(1 ≤ R,C ≤ 25). 每個格子是一個籠子. (尼瑪還要我活麽……)

To get your exercise, the laboratory owners allow you to move between cages.

為了讓你鍛煉身體，實驗室管理員允許你在籠子之間移動。

You can move between cages either by moving right between two adjacent cages in the same row, or by moving down between two adjacent cages in the same column.

你只能向右和向下移動。

You cannot move diagonally, left or up.

你不能斜著移動，也不能向上和向左移動。

Your cage is in one corner of the laboratory, which has the label (1,1) (to indicate top-most row, left-most column).

你所在的籠子是實驗室的左上角，標記為(1,1)

You would like to visit your brother who lives in the cage labelled (R,C) (bottom-most row, right-most column), which is in the other corner diagonally.

你想去右下角的籠子(R,C)里找你的女朋友(尼瑪老鼠也有女盆友麽！！！)

However, there are some cages which you cannot pass through, since they contain cats.

但是有一些籠子是不能經過的，因為裡面有貓（誰說老鼠怕貓麽，還有，管理員有毛病麽……）

Your brother, who loves numbers, would like to know how many different paths there are between your cage and his that do not pass through any cat cage. Write a program to compute this number of cat-free paths.

你女朋友很愛數學，她想要知道有多少條不同的路徑可以從你的籠子到達她的籠子。寫一個程式來計算吧。（這樣的女朋友不要也罷……）

The first line of input contains two integers R and C, separated by one space representing the number of rows and columns (respectively). On the second line of input is the integer K, the number of cages that contain cats. The next K lines each contain the row and column positions (in that order) for a cage that contains a cat. None of the K cat cages are repeated, and all cages are valid positions. Note also that (1,1) and (R,C) will not be cat cages.

第一行包含2個整數R和C，第二行一個整數K，代表包含貓的籠子的個數，接下來K行包含K個不同的位置信息，代表K個包含貓的籠子的位置信息，註意(1,1)和(R,C)這兩個位置是不會有貓的， 否則出題者就沒法活了……

Output the non-negative integer value representing the number of paths between your cage at position (1,1) and your brother’s cage at position (R,C). You can assume the output will be strictly less than 1 000 000 000.

輸出一個非負整數代表你可以去你女朋友籠子里和她啪啪啪的路徑數目，你可以假設這個輸出會嚴格小於1,000,000,000。

樣例輸入 1:

2 3

1

2 1

樣例輸入 2:

3 4

3

2 3

2 1

1 4

樣例輸出 1: 2

樣例輸出 2: 1

也許只有這樣的DP才能給我一絲心靈上的慰藉吧，

有點類似於超簡化版的方格取數。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 void read(int &n)
 7 {
 8     char c='+';int x=0;bool flag=0;
 9     while(c<'0'||c>'9')
10     {c=getchar();if(c=='-')flag=1;}
11     while(c>='0'&&c<='9')
12     {x=x*10+(c-48);c=getchar();}
13     flag==1?n=-x:n=x;
14 }
15 int n,m,k;
16 int map[1001][1001];
17 int main()
18 {
19     read(n);read(m);read(k);
20     for(int i=1;i<=k;i++)
21     {
22         int x,y;
23         read(x);read(y);
24         map[x][y]=-1;
25     }
26     map[1][1]=1;
27     for(int i=1;i<=n;i++)
28         for(int j=1;j<=m;j++)
29         {
30             if(map[i-1][j]!=-1&&map[i][j]!=-1)
31             map[i][j]+=map[i-1][j];
32             if(map[i][j-1]!=-1&&map[i][j]!=-1)
33             map[i][j]+=map[i][j-1];
34         }
35     printf("%d",map[n][m]);
36     return 0;
37 }