C++でグリッド上のポリゴンの辺の数を求める方法を解説

h × w のサイズのグリッドが与えられます。グリッドには「白」と「黒」の2種類のセルがあり、白いセルは「.」、黒いセルは「#」で表されます。グリッド内の複数の黒いセルがひとつのポリゴン(多角形)を形成しており、そのポリゴンが持つ辺の数を求めるのがこの問題の目的です。なお、グリッドの最も外側のセルは必ず白であると仮定して構いません。

例えば、入力が h = 4、w = 4、grid = {"....", ".##.", ".##.", "...."} の場合、出力は 4 になります。これは、黒いセルが正方形を形成しており、正方形には4つの辺があるためです。

解法のアプローチ

この問題は、グリッド上のセルの境界(交点)に注目することで解くことができます。ある交点を囲む4つのセル(左上・右上・左下・右下)を調べ、そのうち黒いセルの数が「1個」または「3個」の場合、その交点はポリゴンの頂点(角)に相当します。つまり、辺を直接数える代わりに、頂点の数を数えることで辺の数が求まります。

具体的な手順は以下の通りです。

sides := 0
for initialize i := 1, when i < h, update (increase i by 1), do:
    for initialize j := 1, when j < w, update (increase j by 1), do:
        bl := 0
        if grid[i - 1, j - 1] is same as '#', then:
            (increase bl by 1)
        if grid[i - 1, j] is same as '#', then:
            (increase bl by 1)
        if grid[i, j - 1] is same as '#', then:
            (increase bl by 1)
        if grid[i, j] is same as '#', then:
            (increase bl by 1)
        if bl is same as 1 or 3, then:
            (increase sides by 1)
return sides

黒いセルの数が2個の場合(直線上の境界)や4個の場合(内部の点)は頂点にならないため、カウントしません。1個の場合は凸な角、3個の場合は凹んだ角に対応します。

C++による実装例

以下に、上記のアルゴリズムをC++で実装した例を示します。

#include <bits/stdc++.h>
using namespace std;
void solve(int h, int w, vector<string> grid){
    int sides = 0;
    for(int i = 1; i < h; i++) {
        for(int j = 1; j < w; j++) {
            int bl = 0;
            if(grid.at(i - 1).at(j - 1) == '#') {
                bl++;
            }
            if(grid.at(i - 1).at(j) == '#') {
                bl++;
            }
            if(grid.at(i).at(j - 1) == '#') {
                bl++;
            }
            if(grid.at(i).at(j) == '#') {
                bl++;
            }
            if(bl == 1 or bl == 3) {
                sides++;
            }
        }
    }
    cout << sides;
}
int main() {
    int h = 4, w = 4;
    vector<string> grid = {"....", ".##.", ".##.", "...."};
    solve(h, w, grid);
    return 0;
}

入力

4, 4, {"....", ".##.", ".##.", "...."}

出力

4

計算量

このアルゴリズムの時間計算量は O(h × w) です。グリッド内の各交点を一度ずつ調べるだけでよいため、サイズの大きなグリッドでも効率的に処理できます。空間計算量は O(1) で、入力のグリッド以外に追加のメモリをほとんど必要としません。