C++で下から右方向へ光を伝送できる鏡の最大数を求める

はじめに

本記事では、0と1だけで構成された正方行列が与えられたとき、「下から右方向へ光を伝送できる鏡」の最大数を求めるアルゴリズムをC++で解説します。

問題の定義

行列の各要素は次の意味を持ちます。

• 0 … 空きセル(何もない場所)
• 1 … 障害物

空きセルの中から鏡を設置できる場所を見つけ、それらの鏡が下から右へ光を伝送できるようにすることを目標とします。

具体的には、鏡がセル [i, j] に配置できるのは、同じ行 i の右側にあるすべてのセルと、同じ列 j の下側にあるすべてのセルに障害物が存在しない場合です。

言い換えると、A[i][j] に鏡を置くためには、A[i+1〜n-1][j] および A[i][j+1〜n-1] のすべてが 0(空)である必要があります。以下の図のようなイメージです。

入力例

Arr[][] = {{0,0,1,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,1,1,0,1},{1,1,1,0,1}}

出力例

No. of mirrors : 3

出力の解説

図に示したとおり、鏡は次の3つのセルに配置できます。

• Arr[1][0] … 1行目・0列目の下側および右側には、障害物となる1が一切ありません。
• Arr[2][0] … 2行目・0列目についても、下側・右側ともにすべて0です。
• Arr[4][4] … 最終セルは0であり、下に行も右に列も存在しないため、条件を自動的に満たします。

アルゴリズムの考え方

本プログラムでは、次の手順で答えを求めています。

• 配列 Arr[][] が0と1からなる行列を表現します。
• 関数 maximumMirror(int mat[][5], int n) は、行列とそのサイズ n を受け取り、設置可能な鏡の最大数を返します。
• 変数 flag は、セル mat[i][j] の下側・右側に障害物がないことを確認するためのフラグです(1 = 障害物なし)。
• count は鏡の個数を表し、初期値は 0 です。
• 行列を左上のインデックス (0, 0) から順番に走査します。
• 各セルが空(0)であれば、まず下方向のセル(k = i+1 から n-1)を調べます。途中で mat[k][j] == 1(障害物)が見つかった場合はループを抜けます。
• 下方向に障害物がなければ、続いて右方向のセル(l = j+1 から n-1)を同様にチェックします。
• 両方向のチェックを終えても flag == 1 のままなら(= どちらにも障害物がない)、count を1増やします。
• 最後に count を戻り値として返します。

C++による実装例

// 下から右へ光を伝送できる鏡の数を求めるC++プログラム
#include <bits/stdc++.h>
using namespace std;

// 下から右へ光を伝送できる鏡の個数を返すメソッド
int maximumMirror(int mat[5][5], int N){
    // 右側・下側のセルがすべて0(障害物なし)であることを記録するフラグ
    int flag = 0;
    int count = 0; // 鏡の個数
    int i, j, k, l;
    // すべてのセルを走査
    for (int i = 0; i < N; i++)
        for (j = 0; j < N; j++) {
            // 次の列・次の行からチェックを開始
            int k = i + 1;
            int l = j + 1;
            if (mat[i][j] == 0) { // 鏡を置ける候補の位置
                while (k < N) { // 下方向の行をチェック
                    if (mat[k][j] == 1) { // 列を固定し、障害物があれば抜ける
                        flag = 0; break;
                    }
                else
                    flag = 1;
                    k++;
                }
                if (flag == 1) // 下方向に障害物がなければ右方向の列をチェック
                    while (l < N) { // 右方向の列をチェック
                        if (mat[i][l] == 1) { // 行を固定し、障害物があれば抜ける
                            flag = 0; break;
                        }
                        else
                            flag = 1;
                        l++;
                    }
                if (flag == 1) // mat[i][j] に鏡を置ける(障害物なし)
                    count++;
            }
        }
    return count;
}

int main(){
    int N = 5;
    // 1が障害物を表す5x5の行列
    int mat[5][5] = {{0,0,1,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,1,1,0,1},{1,1,1,0,1}};
    cout << "下から右へ光を伝送できる最大の鏡の数 :" <<
    maximumMirror(mat, N) << endl;
    return 0;
}

実行結果

Maximum mirrors which can transfer light from bottom to right :3

まとめ

この手法は、各セルごとに下方向と右方向をそれぞれ線形に走査するため、N×N の行列に対する時間計算量は最悪ケースで O(N³) となります。シンプルな全探索アプローチですが、問題の条件(右と下だけを確認すればよい)を素直にコードに反映した分かりやすい実装です。より大規模な入力に対応する場合は、累積和などを用いて「そのセルより下・右に障害物があるか」を前処理で判定すると、O(N²) への高速化も可能です。