1010 过河卒

1010 过河卒

2002年NOIP全国联赛普及组

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 黄金 Gold

题解

 查看运行结果

题目描述 Description

 如图,A 点有一个过河卒,需要走到目标 B 点。卒行走规则:可以向下、或者向右。同时在棋盘上的任一点有一个对方的马(如上图的C点),该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图 C 点上的马可以控制 9 个点(图中的P1,P2 … P8 和 C)。卒不能通过对方马的控制点。

  棋盘用坐标表示,A 点(0,0)、B 点(n,m)(n,m 为不超过 20 的整数,并由键盘输入),同样马的位置坐标是需要给出的(约定: C不等于A,同时C不等于B)。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。

1<=n,m<=15

输入描述 Input Description

 键盘输入    B点的坐标(n,m)以及对方马的坐标(X,Y){不用判错}

输出描述 Output Description

  屏幕输出     一个整数(路径的条数)。

样例输入 Sample Input

 6 6 3 2

样例输出 Sample Output

17

数据范围及提示 Data Size & Hint

如描述

思路:、

用一个数组记录能够到达这里的所有情况

a[i][j]=a[i-1][j]+a[i][j-1]+a[i][j];
 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int vis[1001][1001];
 5 int xx[1001]={-2,-1,+1,+2,+2,+1,-1,-2};
 6 int yy[1001]={+1,+2,+2,+1,-1,-2,-2,-1};
 7 int a[1001][1001];
 8 int n,m;//B(n,m)
 9 int p,q;//马(p,q)
10 int main()
11 {
12     a[0][1]=1;
13     a[1][0]=1;
14     cin>>n>>m>>p>>q;
15     vis[p][q]=1;
16     for(int i=0;i<8;i++)
17     {
18         vis[p+xx[i]][q+yy[i]]=1;
19         a[p+xx[i]][q+yy[i]]=0;
20     }
21     /*for(int i=0;i<=n;i++)
22     {
23         for(int j=0;j<=m;j++)
24         cout<<vis[i][j]<<" ";
25         cout<<endl;
26     }*/
27     for(int i=0;i<=n;i++)
28     {
29         for(int j=0;j<=m;j++)
30         {
31             if(vis[i][j]==1)
32             continue;
33             else
34             {
35                 a[i][j]=a[i-1][j]+a[i][j-1]+a[i][j];
36             }
37         }
38     }
39     //cout<<a[n][m];
40     printf("%d",a[n][m]);
41     return 0;
42 }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

PyTorch实现自由的数据读取

很多前人曾说过,深度学习好比炼丹,框架就是丹炉,网络结构及算法就是单方,而数据集则是原材料,为了能够炼好丹,首先需要一个使用称手的丹炉,同时也要有好的单方和原材...

68170
来自专栏木子昭的博客

<算法>蛇形矩阵求解

? 蛇形矩阵 右下,下左,左上,上右,循环往复~ 解题思路: 在单步前进过程中, x与y, 只能有一个发生变化 每次转向, x与y会发生...

31060
来自专栏崔庆才的专栏

跟繁琐的模型说拜拜!深度学习脚手架 ModelZoo 来袭!

好多天没有更新原创文章了,国庆前的一段时间确实比较忙,整个九月在参加各种面试,另外还有公司的项目,还有自己的毕设,另外还需要准备参加一些活动和讲座,时间排的很紧...

31120
来自专栏生信宝典

R包reshape2,轻松实现长、宽数据表格转换

本文翻译自外文博客,原文链接:https://seananderson.ca/2013/10/19/reshape/

28420
来自专栏Spark学习技巧

干货:基于Spark Mllib的SparkNLP库。

引言 这是来自John Snow Labs工程团队的社区博客和工作,解释了他们对开源Apache Spark自然语言处理(NLP)库的贡献。 Apache Sp...

28280
来自专栏CreateAMind

Deep Learning Book 中文第二十章 深度生成模型

变分自动编码器方法是优雅的,理论上令人愉快的,并且易于实现。它也获得了 出色的结果,是生成式建模中的最先进方法之一

9610
来自专栏大数据文摘

干货 | 男朋友老是说自己R语言很6,快来用这40道题目检测他

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

BZOJ4006: [JLOI2015]管道连接(斯坦纳树,状压DP)

20310
来自专栏新智元

手把手教你如何用Julia做GPU编程(附代码)

GPU是一个大规模并行处理器,具有几千个并行处理单元。 例如,本文中使用的Tesla k80提供4992个并行CUDA内核。 GPU在频率,延迟和硬件功能方面与...

36310
来自专栏青玉伏案

算法与数据结构(八) AOV网的关键路径(Swift版)

上篇博客我们介绍了AOV网的拓扑序列,请参考《数据结构(七) AOV网的拓扑排序(Swift面向对象版)》。拓扑序列中包括项目的每个结点,沿着拓扑序列将项目进行...

23480

扫码关注云+社区

领取腾讯云代金券