C++で解く「Perfect Rectangle」問題：複数の長方形が矩形領域を完全に覆うか判定する方法

問題の概要

N個の軸に平行な長方形が与えられたとき、それらがすべて組み合わさって、ある矩形領域を「隙間も重なりもなく」正確に覆っているかどうかを判定します。各長方形は左下の頂点と右上の頂点で表現され、たとえば単位正方形は [1,1,2,2] と表されます（左下の点が (1,1)、右上の点が (2,2) を意味します）。

たとえば、入力が rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]] の場合、5つの長方形全体がぴったり一つの矩形領域を覆うため、答えは true（1）になります。

解法のポイント

この問題は、次の2つの条件が同時に成り立つかどうかを確認することで解けます。

1. 面積の一致： すべての小さな長方形の面積の総和が、外接矩形（全長方形を含む最小の矩形）の面積と等しいこと。
2. 頂点の出現パターン： 各長方形の4つの頂点を記録し、同じ座標の頂点が出現するたびに取り消していくと、最終的に残る頂点が外接矩形の4隅だけになること。

もし長方形同士に重なりや隙間が存在する場合は、必ずいずれかの条件が崩れるため、この方法で正確に判定できます。計算量は長方形の数を N とすると時間・空間ともに O(N) で、非常に効率的です。

アルゴリズムの手順

1. 頂点を管理するための集合 visited を用意し、面積の合計 area を 0 で初期化します。
2. 外接矩形の境界値として x2 := -inf、x1 := +inf、y2 := -inf、y1 := +inf を設定します。
3. 与えられたリスト内の各長方形 r について、以下を処理します。
   • 境界値を更新：x1 は r[0] との最小値、x2 は r[2] との最大値、y1 は r[1] との最小値、y2 は r[3] との最大値を代入。
   • 面積を加算：area += (r[2] - r[0]) * (r[3] - r[1])
   • 4つの頂点 (r[0], r[1])、(r[0], r[3])、(r[2], r[3])、(r[2], r[1]) を文字列に連結し、その頂点がすでに visited に存在すれば削除、存在しなければ挿入します。
4. すべての処理が終わった後、外接矩形の4隅 (x1, y1)、(x2, y1)、(x1, y2)、(x2, y2) がすべて visited に残っており、かつ visited のサイズがちょうど4であることを確認します。満たさなければ false を返します。
5. 最後に、area == (x2 - x1) * (y2 - y1) が成立していれば true を返します。

C++による実装例

それでは、実際のコードを見て理解を深めましょう。

#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));
}

なお、実務で利用する場合は、座標を連結して文字列キーを作る際に (12,3) と (1,23) のような衝突を避けるため、区切り文字（カンマなど）を挿入しておくと安全です。

入力

{{1, 1, 3, 3}, {3, 1, 4, 2}, {3, 2, 4, 4}, {1, 3, 2, 4}, {2, 3, 3, 4}}

出力

1

出力が 1（true）となったのは、5つの長方形が互いに重ならず、隙間なく矩形領域を完全に覆っているためです。