C++で与えられた行列が有効な縞模様の旗かどうかを判定するコード

ここでは、サイズ n × m の行列を考えます。各セルには 0 から 9 までのいずれかの値が格納され、その値がセルの「色」を表します。この行列は縞模様の旗として成立していなければならず、次の 2 つの条件を満たす必要があります。

• 旗の各行（横方向の並び）は、すべて同じ色のマスで構成されていること
• 上下に隣接する行同士の色は互いに異なること

与えられた行列がこれらの条件を満たす「有効な旗」であるかどうかを判定するのが本記事の目的です。

入力例

この行列の場合、1 行目はすべて 0、2 行目はすべて 1、3 行目はすべて 3 となっており、隣接する行の色もすべて異なるため、有効な旗と判定されます。

解法のアプローチ

この問題は、以下の手順に従って解くことができます。

1. 行列の行数 n と列数 m を取得します。
2. 各行について、先頭の値を基準色 f とし、行内のすべてのセルが f と一致するかを確認します。一致しないセルが 1 つでもあれば無効です。
3. 直前の行の色と現在の行の色が同じ場合も無効です。
4. すべてのチェックを通過すれば true、途中で違反が見つかれば false を返します。

アルゴリズムを擬似コードで表すと次のようになります。

n := 行列の行数
m := 行列の列数
l := 'm'   // 直前の行の色を保持する変数（ダミー値で初期化）
res := 1
for initialize i := 0, when i < n, update (increase i by 1), do:
    f := matrix[i, 0]
    for initialize j := 0, when j < m, update (increase j by 1), do:
        if matrix[i, j] is not equal to f, then:
            res := 0
    if l is same as f, then:
        res := 0
    l := f
return (if res is non-zero, then true, otherwise false)

C++ 実装例

理解を深めるために、実際の C++ コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
bool solve(vector<vector<int>> matrix){
    int n = matrix.size();
    int m = matrix[0].size();
    char l = 'm';
    bool res = 1;
    for (int i = 0; i < n; i++){
        char f = matrix[i][0];
        for (int j = 0; j < m; j++){
            if (matrix[i][j] != f)
                res = 0;
        }
        if (l == f)
            res = 0;
        l = f;
    }
    return res ? true : false;
}
int main(){
    vector<vector<int>> matrix = { { 0, 0, 0 }, { 1, 1, 1 }, { 3, 3, 3 } };
    cout << solve(matrix) << endl;
}

入力

{ { 0, 0, 0 }, { 1, 1, 1 }, { 3, 3, 3 } }

出力

1

出力が 1（true）となり、この行列が有効な縞模様の旗であることが確認できました。

なお、変数 l を文字 'm' で初期化しているのは、セルの値（0〜9 を char 型に変換したもの）が決して 'm' と一致しないためです。これにより、最初の行では「直前の行との色の比較」が必ず通過し、誤って無効と判定されることを防げます。計算量は O(n × m) であり、行列全体を一度走査するだけで済む効率的な手法です。