文档章节

Codevs 1267老鼠的旅行

机智的帝江
 机智的帝江
发布于 2016/10/30 09:59
字数 904
阅读 12
收藏 0

题目描述 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

暴力大法好。。搜索保平安。。我不知道为什么这玩意儿会属于动态规划还是个黄金题目。。个人认为。。青铜的搜索题吧。。。。给搬运工的吐槽给个好评!

#include<iostream>
#include<cstdio>

using namespace std;
const int maxn = 233;
bool map[maxn][maxn];
int r,c,k,ans;

void dfs(int x,int y)
{
    if(x==r && y==c) ans++;
    int down=x+1;
    int right=y+1;
    if(down<=r&&map[down][y]!=1) dfs(down,y);
    if(right<=c&&map[x][right]!=1) dfs(x,right);
}
int main()
{
    cin>>r>>c>>k;
    for(int i=1;i<=k;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        map[a][b]=1;
    }
    dfs(1,1);
    cout<<ans;
    return 0;
}

本文转载自:http://blog.csdn.net/loi__dijiang/article/details/52815681

上一篇: 多源最短路
下一篇: P1346 电车
机智的帝江
粉丝 0
博文 89
码字总数 4734
作品 0
莱芜
程序员
私信 提问
zabbix连不上数据库

zabbix连不上数据库 [root@localhost etc]# tail -f /var/log/zabbix_server.log 1267:20130722:195451.493 [Z3001] connection to database 'zabbix' failed: [2002] Can't connect to loca......

不死鸟007
2016/12/29
0
0
为什么软件开发工期预估都不靠谱

本文的作者Diego Basch是IndexTank公司(被LinkedIn公司收购)的前任CEO,他是看到了Quora上一个有趣的关于讨论软件开发工期估算不准的文章后写下了这篇文章。 有些人认为做一个大型软件项目跟...

虫虫
2012/02/06
4K
29
splay的各种操作与简易讲解

基本操作 插入 和二叉查找树一样,但是插入完成后要splay一下(即伸展),伸展操作下面有 伸展 查找前驱或后驱 例题:codevs1285/洛谷P2286/bzoj1208 宠物收养所 删除和合并 先把要删除的点s...

litble
2017/07/07
0
0
PAT A1056. Mice and Rice (25)

Mice and Rice (25) https://www.patest.cn/contests/pat-a-practise/1056 时间限制 100 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue Mice and Rice is t......

阿豪boy
2017/03/08
36
0
发一个经典的问题。

问: 有 1000 个一模一样的瓶子,其中有 999 瓶是普通的水,有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在,你只有 10 只小白鼠和一星期的时间,如何检验出哪个瓶子里有毒药?...

loki_lan
2012/12/24
1K
21

没有更多内容

加载失败,请刷新页面

加载更多

thinkcmf 渗透测试漏洞修复解决方案

近段时间发现很多APP程序用的是thinkcmf,此程序源码存在getshell漏洞,我们Sine安全紧急对此高危漏洞进行了分析和漏洞修复,攻击者可以通过构造特定的请求包get请求即可在远程服务器上执行任意...

网站安全
31分钟前
6
0
MySQL的IP地址与数字互转原理

一、inet_aton与inet_ntoa inet_aton是把ip地址转为数字的函数,记忆小技巧,inet表示网络相关,在c语言中a习惯性代表字符串,to就是转换的,n代表数字,aton就是字符串转数字,同理inet_nt...

trayvon
43分钟前
6
0
【翻译】全新16英寸MacBook Pro评测:开发人员的梦想成真

要问现在适合开发者用的笔记本,市面上还是有很多选择的,比如Dell的XPS系列,外星人系列(游戏也是杠杠滴),联想拯救者系列,还有形形色色的高配机型,价格也从几千到几万不等。 但是,笔吧...

Dimple91
44分钟前
8
0
IT兄弟连 HTML5教程 CSS3属性特效 CSS3分栏布局

CSS3中新出现的多列布局(multi-column)是传统HTML网页中块状布局模式的有力扩充。这种新语法能够让WEB开发人员轻松的让文本呈现多列显示。我们知道,当一行文字太长时,读者读起来就比较费劲...

老码农的一亩三分地
今天
11
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部