首页 > 试题广场 >

至

[编程题]至
  • 热度指数：2278 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 1024M，其他语言2048M
  • 算法知识视频讲解
\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
分类讨论好难。
发表于 2025-12-20 01:31:28 回复(1)
Java
牛客203596504号头像 牛客203596504号
如果无障碍下两个人到终点的路程不同，那么路程远的永远赶不上路程近的。
无论你如何放置障碍，路程近的走过的路都是路程远的必须走的。
唯一的例外：两人不在同一行，将障碍放在路程近的起点右侧，能让他多两步。
发表于 2025-12-20 01:20:26 回复(1)
周康禧头像 周康禧
两个人的最短路相同，因为只有两行，那么要么在同一个位置，要么刚好错开在不同的行，因为第一行到第二行(2,n)会比第二行的多一步，所以有一种就是(x1!=x2&&y1==y2+1) 然后另一种就是 让下面的右边防障碍，让它往上多一步，那么第一行的就在这个左边就行了(x1!=x2&&y2==y1+1&&y2<n-1)，注意因为这个情况第二行右边必须要有一个地方方障碍所以还得y2<n-1
void solve(){   
    int n;
    cin>>n;
    int x1,x2,y1,y2;
    cin>>x1>>y1;
    cin>>x2>>y2;
    if(x1>x2){
        swap(x1,x2);
        swap(y1,y2);
    }
    if((x1==x2&&y1==y2)||(x1!=x2&&y1==y2+1)||(x1!=x2&&y2==y1+1&&y2<n-1)){
        cout<<"YES"<<'\n';
    }else{
        cout<<"NO"<<'\n';
    }
}   



发表于 2025-12-20 23:24:40 回复(0)
提交观点

问题信息

难度：
3条回答 10浏览

热门推荐

相关试题

至

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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