N 축으로 정렬된 직사각형이 있다고 가정하면 모두 함께 직사각형 영역의 정확한 덮개를 형성하는지 여부를 확인해야 합니다. 여기에서 각 사각형은 왼쪽 아래 점과 오른쪽 위 점으로 표시됩니다. 따라서 단위 제곱은 [1,1,2,2]로 표시됩니다. (왼쪽 아래 지점은 (1, 1)이고 오른쪽 상단 지점은 (2, 2)입니다).
따라서 입력이 직사각형 =[[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4]인 경우 [2,3,3,4]], 5개의 직사각형이 모두 직사각형 영역의 정확한 덮개를 형성하므로 출력은 true가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
방문한 한 세트 정의
-
면적 :=0
-
x2 :=-inf, x1 :=inf
-
y2 :=-inf, y1 :=inf
-
주어진 목록의 각 r에 대해 re -
-
x1 :=r[0] 및 x1의 최소값
-
x2 :=r[2] 및 x2의 최대값
-
y1 :=r[1] 및 y1의 최소값
-
y2 :=r[3] 및 y2의 최대값
-
면적 :=면적 + ((r[2] - r[0]) * (r[3] - r[1]))
-
s1 :=r[0] r[1] 연결
-
s2 :=r[0] r[3] 연결
-
s3 :=r[2] r[3] 연결
-
s4 :=r[2] r[1] 연결
-
s1을 방문하면 -
-
방문에서 s1 삭제
-
-
그렇지 않으면
-
방문에 s1 삽입
-
-
s2를 방문하면 -
-
방문에서 s2 삭제
-
-
그렇지 않으면
-
방문에 s2 삽입
-
-
s3를 방문하면 -
-
방문에서 s3 삭제
-
-
그렇지 않으면
-
방문에 s3 삽입
-
-
s4를 방문하면 -
-
방문에서 s4 삭제
-
-
그렇지 않으면
-
방문에 s4 삽입
-
-
-
s1 :=x1과 y1 연결
-
s2 :=x2와 y1 연결
-
s3 :=x1과 y2 연결
-
s4 :=x2와 y2 연결
-
s1, s2, s3, s4가 모두 방문되지 않은 경우
-
거짓을 반환
-
-
면적이 ((x2 - x1) * (y2 - y1))
와 같으면 true를 반환합니다.
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isRectangleCover(vector<vector<int>> &re) {
unordered_set<string> visited;
int area = 0;
int x2 = INT_MIN;
int x1 = INT_MAX;
int y2 = INT_MIN;
int y1 = INT_MAX;
for (auto &r : re) {
x1 = min(r[0], x1);
x2 = max(r[2], x2);
y1 = min(r[1], y1);
y2 = max(r[3], y2);
area += (r[2] - r[0]) * (r[3] - r[1]);
string s1 = to_string(r[0]) + to_string(r[1]);
string s2 = to_string(r[0]) + to_string(r[3]);
string s3 = to_string(r[2]) + to_string(r[3]);
string s4 = to_string(r[2]) + to_string(r[1]);
if (visited.count(s1)) {
visited.erase(s1);
}
else
visited.insert(s1);
if (visited.count(s2)) {
visited.erase(s2);
}
else
visited.insert(s2);
if (visited.count(s3)) {
visited.erase(s3);
}
else
visited.insert(s3);
if (visited.count(s4)) {
visited.erase(s4);
}
else
visited.insert(s4);
}
string s1 = to_string(x1) + to_string(y1);
string s2 = to_string(x2) + to_string(y1);
string s3 = to_string(x1) + to_string(y2);
string s4 = to_string(x2) + to_string(y2);
if (!visited.count(s1) || !visited.count(s2) || !visited.count(s3) || !visited.count(s4) || visited.size() != 4)
return false;
return area == (x2 - x1) * (y2 - y1);
}
};
main() {
Solution ob;
vector<vector<int>> v = {{1, 1, 3, 3}, {3, 1, 4, 2}, {3, 2, 4, 4}, {1, 3, 2, 4}, {2, 3, 3, 4}};
cout << (ob.isRectangleCover(v));
} 입력
{{1, 1, 3, 3}, {3, 1, 4, 2}, {3, 2, 4, 4}, {1, 3, 2, 4}, {2, 3, 3, 4}} 출력
1