# 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).

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).

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.

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 ﬁrst 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.

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.

2 3

1

2 1

3 4

3

2 3

2 1

1 4

``` 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 }```

1811 篇文章121 人订阅

0 条评论

## 相关文章

### 洛谷 P1876 开灯(思维，枚举，规律题)

P1876 开灯 题目背景 该题的题目是不是感到很眼熟呢? 事实上，如果你懂的方法，该题的代码简直不能再短。 但是如果你不懂得呢？那。。。（自己去想） 题目描述...

30660

### 详解斯坦纳点及斯坦纳树及模版归纳总结

①什么是斯坦纳点？ 　　假设原来已经给定了个点，库朗等指出需要引进的点数至多为，此种点称为斯坦纳点。过每一斯坦纳点，至多有三条边通过。若为三条边，则它们两两交成...

89660

31760

20030

41960

### 约瑟夫问题方法总结

n个人围成一个圈，每个人分别标注为1、2、...、n，要求从1号从1开始报数，报到k的人出圈，接着下一个人又从1开始报数，如此循环，直到只剩最后一个人时，该人即...

37380

482100

21600

### Codeforces Round #412 (rated, Div. 2, base on VK Cup 2017 Round 3)(A.B.C，3道暴力题，C可二分求解)

A. Is it rated? time limit per test：2 seconds memory limit per test：256 megabyte...

37870

### 泛函编程（17）－泛函状态－State In Action

对OOP编程人员来说，泛函状态State是一种全新的数据类型。我们在上节做了些介绍，在这节我们讨论一下State类型的应用：用一个具体的例子来示范如何使...

21080