数据结构
网络
关系数据库管理系统 (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 次浏览
广告