C++でバイナリ行列内の1から形成される図形の周囲長を求める方法

この問題では、0と1のみで構成される n×m のサイズのバイナリ行列 bin[][] が与えられます。求めるのは、行列内の 1 から形成される図形の周囲長(ペリメーター)です。

周囲長とは、図形を四方すべてから取り囲む外周の長さのことです。

例えば、値が1のセルが1つだけある場合、その周囲長は 4 となります。

入出力例

入力

bin[][] = [1, 0]
          [1, 0]

出力

6

説明

セル (0,0) と (1,0) がつながっており、縦2・横1の長方形を形成しています。したがって、周囲長は 2+2+1+1 = 6 となります。

解法アプローチ

この問題のシンプルな解き方は、行列内のすべての1を見つけ、それぞれが周囲長にどれだけ寄与するかを計算し、その合計を求めるというものです。

行列内の1つの1が周囲長に寄与する度合いは以下の通りです。

• 最大の寄与は4: その1が上下左右に隣接する1を持たない(孤立している)場合。
• 最小の寄与は0: その1が上下左右すべてを1に囲まれている場合。

つまり、各セルの周囲長への寄与は「4 − 隣接する1の数」で計算できます。行列の各要素について1かどうかを確認し、1であればその上下左右の隣接セルを調べて寄与を求め、最後にすべてを合計します。

実装例(C++)

#include<iostream>
using namespace std;
#define R 3
#define C 5
int contibutionToPerimeter(int mat[][C], int i, int j) {
    int neighbours = 0;
    if (i > 0 && mat[i - 1][j])
        neighbours++;
    if (j > 0 && mat[i][j - 1])
        neighbours++;
    if (i < R-1 && mat[i + 1][j])
        neighbours++;
    if (j < C-1 && mat[i][j + 1])
        neighbours++;
    return (4 - neighbours);
}
int calcPerimeter(int mat[R][C]){
    int perimeter = 0;
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            if (mat[i][j] == 1)
                perimeter += contibutionToPerimeter(mat, i ,j);
    return perimeter;
}
int main() {
    int mat[R][C] = { {0, 1, 0, 0, 0},
    {1, 1, 1, 1, 0},
    {1, 1, 0, 1, 1} };
    cout<<"1から形成される図形の周囲長は "<<calcPerimeter(mat);
    return 0;
}

出力

1から形成される図形の周囲長は 18

計算量

• 時間計算量: O(n×m) — 行列の全セルを一度ずつ走査します。
• 空間計算量: O(1) — 追加の記憶領域は定数分のみ使用します。