首页 > 试题广场 >

至

[编程题]至
\hspace{15pt}⭐我喜欢在雨天屋檐下追溯滞后的频率
\hspace{15pt}Bingbong 给定一个大小为 2\times n（2 行 n 列）的矩阵，我们使用 (i,j) 表示矩阵中从上往下数第 i 行和从左往右数第 j 列的位置，初始时每个位置都为空地。Bing 初始位于 (x_1,y_1)，Bong 初始位于 (x_2,y_2)，两个人的位置可以重复。
\hspace{15pt}他们每次移动会以向上、向下或者向右移动一个单元格，直到移动到终点 (2,n)，前提是不能超出边界。

\hspace{15pt}一个位置若放置了障碍物，则无法进入。现在你可以在矩阵上放置任意数量的障碍物（也可以不放置障碍物），需要满足以下条件：
\hspace{23pt}\bullet\,两个人的初始位置和终点不得放置障碍物。
\hspace{23pt}\bullet\,两个人都至少存在一条路径可以到达 (2,n)。
\hspace{23pt}\bullet\,使得 Bing 和 Bong 两个人移动到终点的最短路径长度相等。
\hspace{15pt}请判断是否存在满足条件的放置方法，若存在输出 \text{YES}，否则输出 \text{NO}。

输入描述:
\hspace{15pt}第一行输入一个整数 n \left(1\leqq n\leqq 10^5\right)，表示矩阵的列长。 
\hspace{15pt}第二行输入两个整数 x_1,y_1 \left(1\leqq x_1\leqq 2;\ 1\leqq y_1\leqq n\right)，表示 Bing 的起始位置。 
\hspace{15pt}第三行输入两个整数 x_2,y_2 \left(1\leqq x_2\leqq 2;\ 1\leqq y_2\leqq n\right)，表示 Bong 的起始位置。


输出描述:
\hspace{15pt}请判断是否存在满足条件的放置方法，若存在输出 \text{YES}，否则输出 \text{NO}。
示例1

输入

6
1 1
1 1

输出

YES
示例2

输入

6
1 1
1 2

输出

NO
算法知识视频讲解
添加回答
Reisentyan头像 Reisentyan
分类讨论好难。
发表于 今天 01:31:28 回复(1)
Java
牛客203596504号头像 牛客203596504号
如果无障碍下两个人到终点的路程不同，那么路程远的永远赶不上路程近的。
无论你如何放置障碍，路程近的走过的路都是路程远的必须走的。
唯一的例外：两人不在同一行，将障碍放在路程近的起点右侧，能让他多两步。
发表于 今天 01:20:26 回复(1)
提交观点

问题信息

难度：
2条回答 7浏览

热门推荐

相关试题

至

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号