IT知识库 购物 网址 游戏 小说 歌词 快照 开发 股票 美女 新闻 笑话 | 汉字 软件 日历 阅读 下载 图书馆 编程 China
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题 autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程 CSS/HTML/Xhtml html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
站长资讯 .NET新手 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA VisualStudio ASP.NET-MVC .NET控件开发 EntityFramework WinRT-Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动 Html-Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP OracleERP DynamicsCRM K2 BPM 信息安全 企业信息 Android开发 iOS开发 WindowsPhone WindowsMobile 其他手机 敏捷开发 项目管理 软件工程 SQLServer Oracle MySQL NoSQL 其它数据库 Windows7 WindowsServer Linux
  IT知识库 -> C++ -> 1267 老鼠的旅行 2012年CCC加拿大高中生信息学奥赛 -> 正文阅读

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

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 ?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.
第一行包含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 }

上一篇文章      下一篇文章      查看所有文章
加:2017-06-30 21:37:26  更:2017-06-30 21:37:53 
 
  C++ 最新文章
关于poin与references
019:别叫,这个大整数已经很简化了!
c++智能指针详解
BZOJ1269: [AHOI2006]文本编辑器editor
洛谷P3835 【模板】可持久化平衡树
洛谷P2925 [USACO08DEC]干草出售Hay For Sa
【深入Cocos2d
STL Traits编程技法
QML与Qt C++ 交互机制探讨与总结
【poj 2431】Expedition
技术频道: 站长资讯 .NET新手区 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA Visual Studio ASP.NET MVC .NET控件开发 Entity Framework WinRT/Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动设计 Html/Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP Oracle ERP Dynamics CRM K2 BPM 信息安全 企业信息化其他 Android开发 iOS开发 Windows Phone Windows Mobile 其他手机开发 敏捷开发 项目与团队管理 软件工程其他 SQL Server Oracle MySQL NoSQL 其它数据库 Windows 7 Windows Server Linux
脚本语言: vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题 autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程
网站开发: CSS/HTML/Xhtml html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 三丰软件 开发 中国文化 网文精选 阅读网 看图 日历 万年历 2018年8日历
2018-8-16 4:57:28
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT知识库