資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++程式中檢查是否可以連線圓圈中方塊的查詢
在這個問題中，我們給定一個數字n，表示位於圓周邊緣的n個方塊。並且有Q個查詢，每個查詢包含兩個整數a和b。我們的任務是建立一個程式來解決這些查詢，以檢查是否可以連線圓圈中的方塊。
問題描述 − 要解決每個查詢，我們需要檢查用杆連線方塊a和方塊b的可能性，同時不能干擾上一個查詢中方塊的連線。我們需要根據條件列印可以或不可以。
讓我們來看一個例子來理解這個問題：
輸入
n = 6 Q = 3 Queries = {{1, 3}, {2, 5}, {4, 5}}輸出
Possible Not possible Possible
解釋
實線是可以連線的杆，而虛線是不能連線的線。
解決方案
解決這個問題的一個簡單方法是為每個查詢查詢解，我們將查詢給定的方塊a和方塊b是否可以連線。為此，我們需要將上一個查詢的值作為參考點，然後檢查連線是否可行。
讓我們考慮查詢(i-1)的方塊a和b作為參考點ref1和ref2。然後查詢點a和b是否位於杆的兩側。
為此，我們將檢查兩個條件：
條件1 − if (ref1 < a < ref2 and ref2 < b < n)
條件2 − if (ref1 < b < ref2 and ref2 < a < n)
在這兩種情況下，結果都將是不可能的。
這是一個程式，用於說明我們解決方案的工作原理：
示例
#include <iostream>
using namespace std;
int printSolutoin(int n, int a, int b, int ref1, int ref2, int lastConn){
if(lastConn == 0 && a != b)
return 1;
int temp;
if(a > b){
temp = a;
a = b;
b = temp;
}
if(ref1 > ref2){
temp = ref1;
ref1 = ref2;
ref2 = temp;
}
if( ( ref1 < a && a < b && b < ref2) )
return 1;
if( (ref1 <= a <= ref2) && (ref2 <= b <= n) ) return 0;
else if( (ref1 <= b <= ref2) && (ref2 <= a <= n) )
return 0;
return 0;
return 1;
}
void solveAllQueries(int n, int q, int query[][2]){
int lastConn = printSolutoin(n, query[0][0], query[0][1], 0, 0, 0);
lastConn?cout<<"Possible\n":cout<<"Not Possible\n";
for(int i = 1; i < q; i++){
lastConn = printSolutoin(n, query[i][0], query[i][1], query[i - 1][0], query[0][1], lastConn);
lastConn?cout<<"Possible\n":cout<<"Not Possible\n";
}
}
int main() {
int n = 6;
int Q = 3;
int query[Q][2] = {{1, 3}, {2, 5}, {4, 5}};
return 0;
}輸出
Possible Not Possible Possible
更新於：2020-12-22
66 次瀏覽
廣告