1267 老鼠的旅行 2012年CCC加拿大高中生信息学奥赛

题目描述 Description

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.

你女朋友很爱数学,她想要知道有多少条不同的路径可以从你的笼子到达她的笼子。写一个程序来计算吧。(这样的女朋友不要也罢……)

输入描述 Input Description

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 Description

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。

样例输入 Sample Input

样例输入 1:

2 3

1

2 1

样例输入 2:

3 4

3

2 3

2 1

1 4

样例输出 Sample Output

样例输出 1: 2

样例输出 2: 1

数据范围及提示 Data Size & Hint

也许只有这样的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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

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

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

30660
来自专栏小樱的经验随笔

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

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

89660
来自专栏数据结构与算法

P1133 教主的花园

题目描述 教主有着一个环形的花园,他想在花园周围均匀地种上n棵树,但是教主花园的土壤很特别,每个位置适合种的树都不一样,一些树可能会因为不适合这个位置的土壤而损...

31760
来自专栏Java3y

Map集合、散列表、红黑树介绍

20030
来自专栏程序员互动联盟

【编程之美】最短路径

最短路径 任意给定两个数字A和B,通过将A和6个数(7,-7,5,-5,12,-12)做加减运算,运算次数不限,每个数可以被使用多次,求从A到B最少要经过多少次...

41960
来自专栏小樱的经验随笔

约瑟夫问题方法总结

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

37380
来自专栏聊聊技术

原 初学算法 - 求凸包的Garham's

482100
来自专栏Jack-Cui

第十五天、杨辉三角

题目 输出杨辉三角 1、程序分析     利用杨辉三角形的特性,进行求解。 2、程序实现 /***************************...

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

扫码关注云+社区

领取腾讯云代金券