C++で行列内の空洞（キャビティ）の数を見つける方法

空洞（キャビティ）とは

ここでは、与えられた行列の中に存在する「空洞（キャビティ）」の数を求める問題を考えます。ある要素が空洞とみなされるのは、その周囲に隣接するすべての要素（上下左右および斜め方向）が、その要素よりも大きい場合です。

例として、次のような行列を見てみましょう。

この行列の場合、中央の「1」は周囲のすべての要素（4, 7, 4, 5, 5, 6, 5, 6）よりも小さいため空洞となり、出力は 1 になります。

アルゴリズムの考え方

基本的なアプローチはシンプルで、各要素について周囲の要素を順番にチェックし、すべての隣接要素より小さければ空洞としてカウントします。

ただし、このままでは行列の端や角にある要素の扱いが煩雑になります。そこで、元の行列の外周に INT_MAX（事実上の無限大として機能する大きな値）で埋めた境界を追加しておくことで、端の要素も同じ条件式で統一的に判定できるようになります。

C++による実装例

#include<iostream>
#define MAX 100
using namespace std;
int numberOfCavities(int array[][MAX], int n) {
    int arr[n + 2][n + 2];
    int count = 0;
    for (int i = 0; i < n + 2; i++) {
       for (int j = 0; j < n + 2; j++) {
          if ((i == 0) || (j == 0) || (i == n + 1) || (j == n + 1))
             arr[i][j] = INT_MAX;
          else
             arr[i][j] = array[i - 1][j - 1];
       }
    }
    for (int i = 1; i <= n; i++) {
       for (int j = 1; j <= n; j++) {
          if ((arr[i][j] < arr[i - 1][j]) && (arr[i][j] < arr[i + 1][j]) && (arr[i][j] < arr[i][j - 1])
             && (arr[i][j] < arr[i][j + 1]) && (arr[i][j] < arr[i - 1][j - 1]) && (arr[i][j] < arr[i + 1][j + 1])
             && (arr[i][j] < arr[i - 1][j + 1]) && (arr[i][j] < arr[i + 1][j - 1])) count++;
       }
    }
    return count;
}
int main() {
    int a[][MAX] = { { 4, 5, 6 }, { 7, 1, 5 }, { 4, 5, 6 }};
    int n = 3;
    cout << "Number of cavities: " << numberOfCavities(a, n);
}

実行結果

Number of cavities: 1

この実装では、まず元の行列を (n+2)×(n+2) の新しい配列にコピーし、外周を INT_MAX で埋めています。その後、各要素について上下左右と斜めの8方向の隣接要素と比較し、すべてより小さい場合にのみカウントを増やしています。計算量は O(n²) であり、各要素を一度ずつ調べるだけで済むため効率的です。