数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中查找是否可以通过给定的转换到达终点
假设我们在 x 轴上有 n 个点，以及这些点之间允许的转换列表。查找是否可以通过仅使用这些转换从起点到达终点。所以，如果点 x1 和 x2 之间存在转换，那么我们可以从点 x 移动到 x1 和 x2 之间的任何中间点，或者直接移动到 x2。因此，如果 n = 5，并且转换是 0 到 2、2 到 4 和 3 到 5。那么输出将是 YES。从 0→2→3→5 存在一条路径。
我们必须根据对的第一个元素对列表进行排序。然后从列表的第二对开始，检查对的第一个元素是否在上一对的第二个元素和当前对的第二个元素之间。此条件用于检查两个连续对之间是否存在路径。最后，我们将检查我们到达的点是否是目标点，以及我们开始的点是否是起点。如果是，则显示 YES，否则显示 NO。
示例
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
bool isPathPairFound(int n, vector<pair<int, int> > array) {
sort(array.begin(),array.end());
int start_point = array[0].first;
int end_point=array[0].second;
for (int i=1; i<n; i++) {
if (array[i].first > end_point)
break;
end_point=max(end_point,array[i].second);
}
return (n <= end_point && start_point==0);
}
int main() {
vector<pair<int, int> > array;
array.push_back(make_pair(0,2));
array.push_back(make_pair(2,4));
array.push_back(make_pair(3,5));
if (isPathPairFound(5,array))
cout << "Path has found";
else
cout << "NO Path has found";
}输出
Path has found
更新于: 2019-12-18
65 次查看
广告