查找是否有可能通过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