C++でマトリックス内のソート済み行をすべてカウントする方法

このチュートリアルでは、行列（マトリックス）の中から「ソート済みの行」がいくつあるかを数えるC++プログラムについて解説します。

具体的には、m×n のサイズの行列が与えられ、その中から昇順または降順のいずれかで整列されている行をすべてカウントするのが課題です。

アルゴリズムのポイント

各行に対して以下の2つの判定を行い、どちらかに該当すればカウントします。

• 昇順の判定：各行を左から右へ走査し、隣接する要素が常に増加していれば昇順とみなします。
• 降順の判定：各行を右から左へ走査し、隣接する要素が常に減少していれば降順とみなします。

計算量は O(m×n) となり、行列の全要素を一度ずつ確認するだけで効率的に処理できます。

サンプルコード

#include <bits/stdc++.h>
#define MAX 100
using namespace std;
// ソート済みの行をカウントする関数
int count_srows(int mat[][MAX], int r, int c){
    int result = 0;
    // 昇順の行をチェック
    for (int i=0; i<r; i++){
        int j;
        for (j=0; j<c-1; j++)
        if (mat[i][j+1] <= mat[i][j])
           break;
        if (j == c-1)
           result++;
    }
    // 降順の行をチェック
    for (int i=0; i<r; i++){
        int j;
        for (j=c-1; j>0; j--)
           if (mat[i][j-1] <= mat[i][j])
              break;
        if (c > 1 && j == 0)
           result++;
    }
    return result;
}
int main(){
    int m = 4, n = 5;
    int mat[][MAX] = {{1, 2, 3, 4, 5}, {4, 3, 1, 2, 6}, {8, 7, 6, 5, 4}, {5, 7, 8, 9, 10}};
    cout << count_srows(mat, m, n);
    return 0;
}

実行結果

3

結果の解説

この例では、以下の3つの行がソート済みと判定されています。

• {1, 2, 3, 4, 5} … 昇順
• {8, 7, 6, 5, 4} … 降順
• {5, 7, 8, 9, 10} … 昇順

一方、{4, 3, 1, 2, 6} は増減が混在しているため、カウント対象外となります。