洛谷p1002过河卒

2024-02-23 01:36
文章标签 洛谷 过河 p1002

本文主要是介绍洛谷p1002过河卒,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

[NOIP2002 普及组] 过河卒

题目描述

棋盘上 A A A 点有一个过河卒,需要走到目标 B B B 点。卒行走的规则:可以向下、或者向右。同时在棋盘上 C C C 点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示, A A A ( 0 , 0 ) (0, 0) (0,0) B B B ( n , m ) (n, m) (n,m),同样马的位置坐标是需要给出的。

现在要求你计算出卒从 A A A 点能够到达 B B B 点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。

输入格式

一行四个正整数,分别表示 B B B 点坐标和马的坐标。

输出格式

一个整数,表示所有的路径条数。

样例 #1

样例输入 #1

6 6 3 3

样例输出 #1

6

提示

对于 100 % 100 \% 100% 的数据, 1 ≤ n , m ≤ 20 1 \le n, m \le 20 1n,m20 0 ≤ 0 \le 0 马的坐标 ≤ 20 \le 20 20

【题目来源】

NOIP 2002 普及组第四题

详解参考https://chiaromain.blog.luogu.org/solution-p1002

#include<bits/stdc++.h>
using namespace std;#define ll long long
int fx[] = {0, -2, -1, 1, 2, 2, 1, -1, -2};
int fy[] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
//马可以走到的位置int bx, by, mx, my;
ll f[40][40];
bool s[40][40]; //判断这个点有没有马拦住
int main()
{cin >> bx >> by >> mx >> my;//坐标+2以防越界bx += 2;by += 2;mx += 2;my += 2;//初始化f[2][1] = 1;//标记马的位置s[mx][my] = 1;for(int i = 1; i <= 8; i++){int x = mx + fx[i];int y = my + fy[i];s[x][y] = 1;}for(int i = 2; i <= bx; i++){for(int j = 2; j <= by; j++){// 如果被马拦住就直接跳过if(s[i][j])continue;//状态转移方程f[i][j] = f[i - 1][j] + f[i][j - 1];}}cout << f[bx][by] <<endl;return 0;
}

这篇关于洛谷p1002过河卒的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/737120

相关文章

高精度计算(代码加解析,洛谷p1601,p1303)除法待更新

目录 高精度加法 高精度减法 高精度乘法 高精度加法 我们知道在c++语言中任何数据类型都有一定的表示范围。当两个被加数很大时,正常加法不能得到精确解。在小学,我们做加法都采用竖式方法。那么我们也只需要按照加法进位的方式就能得到最终解。 8 5 6+ 2 5 5-------1 1 1 1 加法进位: c[i] = a[i] + b[i];if(c[i] >=

洛谷 凸多边形划分

T282062 凸多边形的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 先整一个半成品,高精度过两天复习一下补上 #include <iostream>#include <algorithm>#include <set>#include <cstring>#include <string>#include <vector>#include <map>

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机(二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机(二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用,那个马的关系,后面就注意,dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ

能量项链,洛谷

解释:  环形dp问题还是考虑将环拉直,可以参考我上一篇文章:环形石子合并 [2 3 5 10 2] 3 5 10 将环拉直,[]内是一个有效的区间,可以模拟吸收珠子的过程,         如[2 3 5] <=>(2,3)(3,5)    2是头,3是中间,5是尾 len >= 3:因为最后[2 10 2]是最小的可以合并的有效区间 len <= n + 1因为[2 3

洛谷P5490扫描线

0是最小的数字,将一个线段看成一个区间,对于一个矩形,从下扫到上,入边为1,而出边为-1,意思是将这个区间上的所有点加1(区间修改).把线段表示为Line[i],其中记录了l,r,h,tag,左右端点,高度,入边还是出边(1或-1) 那么每次区间修改后不为0的区间它的值可能是1,2,3或者是其它数字,这不好统计,可以将它转化一下,0是不是表示没有被覆盖过的地方,我们只要统计0的个数然后用总长减去

挤牛奶洛谷uasco

题目描述 三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶。第一个农民在300秒(从5点开始计时)给他的牛挤奶,一直到1000秒。第二个农民在700秒开始,在 1200秒结束。第三个农民在1500秒开始2100秒结束。期间最长的至少有一个农民在挤奶的连续时间为900秒(从300秒到1200秒),而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300秒(从1200秒到1500秒)。

A*算法解决传教士—野人过河问题

A*算法解决传教士—野人过河问题 算法原理 1、A算法的基本原理分析; 在或图的一般搜索算法中,如果在搜索过程的步骤⑦利用估价函数f(n)=g(n)+h(n)对open表中的节点进行排序,则该搜索算法为A算法。 g(n):从初始节点到n的实际代价 因为n为当前节点,搜索已达到n点,所以g(n)可计算出。 h(n):启发函数,从n到目标节点的最佳路径的估计代价。 因为尚未找到解路径,所以h(n)

洛谷刷题(7)

P8738 [蓝桥杯 2020 国 C] 天干地支 题目描述 古代中国使用天干地支来记录当前的年份。 天干一共有十个,分别为:甲(jiǎ)、乙(yǐ)、丙(bǐng)、丁(dīng)、戊 (wù)、己(jǐ)、庚(gēng)、辛(xīn)、壬(rén)、癸(guǐ)。 地支一共有十二个,分别为:子(zǐ)、丑(chǒu)、寅(yín)、卯(mǎo)、辰(chén)、巳(sì)、午(wǔ)、

C++ 洛谷 哈希表(对应题库:哈希,hash)习题集及代码

马上就开学了,又一个卷季,不写点东西怎么行呢?辣么,我不准备写那些dalao们都懂得,熟练的,想来想去,最终还是写哈希表吧!提供讲解&题目&代码解析哦! 奉上题目链接: 洛谷题目 - 哈希,hash 1、哈希、哈希表(hash)简介 哈希(Hash)是一种将任意长度的输入映射为固定长度输出的算法。哈希函数的输出值称为哈希值或散列值。哈希函数具有以下特性: 确定性:对于相同的输入