資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告