C++のマトリックスで安全なセル（植物）を見つける方法

問題概要

文字から構成される2次元マトリックス mat[][] が与えられたとします。各セルには次の3種類の文字が格納されています。

• Z：ゾンビ
• P：植物
• *：更地（何もない土地）

ゾンビは、自分の隣接セル（上下左右だけでなく斜め方向を含む8方向）にいる植物を攻撃することができます。このとき、ゾンビの攻撃を受けることなく安全に生存できる植物の数を求めるのが本記事の目的です。

例として、次のようなマトリックスを考えてみましょう。

この場合、ゾンビから安全な植物はわずか2つだけです。

アルゴリズムの考え方

アプローチは非常にシンプルで、以下の手順で実現できます。

1. マトリックスの全要素を1つずつ走査します。
2. 現在注目しているセルが植物「P」であった場合、その周囲8方向にゾンビ「Z」が存在するかどうかを確認します。
3. 周囲にゾンビが1つも存在しなければ、その植物は安全と判断し、カウントを1増やします。

走査が完了した時点でのカウント値が、求める「安全なセルの数」となります。

C++による実装例

#include<iostream>
using namespace std;
bool isZombie(int i, int j, int r, int c, string mat[]) {
    if (i < 0 || j < 0 || i >= r || j >= c || mat[i][j] != 'Z')
        return false;
    return true;
}
int countSafeCells(string matrix[], int row, int col) {
    int i, j, count = 0;
    for (i = 0; i < row; i++) {
        for (j = 0; j < col; j++) {
            if (matrix[i][j] == 'P') {
                if (!isZombie(i - 1, j - 1, row, col, matrix) && !isZombie(i - 1, j, row, col, matrix)
                    && !isZombie(i - 1, j + 1, row, col, matrix) && !isZombie(i, j - 1, row, col, matrix)
                    && !isZombie(i, j, row, col, matrix) && !isZombie(i, j + 1, row, col, matrix)
                    && !isZombie(i + 1, j - 1, row, col, matrix) && !isZombie(i + 1, j, row, col, matrix)
                    && !isZombie(i + 1, j + 1, row, col, matrix)) {
                    count++;
                }
            }
        }
    }
    return count;
}
int main() {
    string mat[] = { "**P*", "Z***", "*P**", "***P" };
    int row = sizeof(mat) / sizeof(mat[0]);
    int col = mat[0].length();
    cout << "Number of safe cells: " << countSafeCells(mat, row, col);
}

出力結果

Number of safe cells: 2

コードのポイント解説

isZombie() 関数：指定された座標 (i, j) のセルがゾンビかどうかを判定する補助関数です。座標がマトリックスの範囲外の場合や、そのセルが「Z」以外の場合は false を返します。これにより、マトリックスの端や角にある植物についても、配列の範囲外アクセスを起こすことなく安全にチェックできます。

countSafeCells() 関数：二重ループでマトリックス全体を走査し、植物セルを見つけるたびに、その周囲のセルに対して isZombie() を呼び出します。すべての結果が false であれば、その植物はどのゾンビにも隣接していないため安全とみなし、カウントを増やします。

main() 関数：サンプル用のマトリックスを定義し、行数・列数を自動的に計算したうえで countSafeCells() を呼び出し、結果を標準出力に表示します。

この手法は計算量 O(row × col × 9) で済むため、小〜中規模のマトリックスであれば効率的に動作します。より大規模なデータを扱う場合は、ゾンビの位置を事前にリスト化しておき、各植物との距離を比較する方式なども検討するとよいでしょう。