C++でn×nの正方形ボード上の勝利マスを数える方法

n×n の正方形ボードがあり、Amal（アマル）と Bimal（ビマル）がゲームを行っています。二人はゲーム中、独自のルールに従ってボードの各マスに数字を書き込んでいきます。現在見えているのはゲーム終了後の盤面です。どちらが勝者かを判定するには、「勝利マス」の数を数える必要があります。

あるマスが勝利マスであるかは、次のように判定します。

• そのマスと同じ列にあるすべての数字の合計を求めます。
• 同じ行にあるすべての数字の合計を別途求めます。
• 列の合計が行の合計より厳密に大きい場合、そのマスは勝利マスとなります。

たとえば、次のような入力が与えられたとします。

このときの出力は 6 になります。勝利マスに該当するのは、下の表でオレンジ色で示した6つのマスです。

アルゴリズムの手順

この問題は次の手順で解くことができます。

1. 勝利マスを数える変数 t を 0 で初期化します。
2. 盤面上のすべてのマス (i, j) を走査し、行 i の合計 s と列 j の合計 l をそれぞれ計算します。
3. l > s が成り立てば t を 1 増やします。
4. すべてのマスを調べ終えたら、t を結果として返します。

C++による実装例

理解を深めるために、実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(vector<vector<int>> M){
    int t = 0;
    int n = M.size();
    for (int i = 0; i <= n - 1; i++)
    for (int j = 0; j <= n - 1; j++){
        int s = 0;
        int l = 0;
        for (int k = 0; k <= n - 1; k++){
            s += M[i][k];
            l += M[k][j];
        }
        if (l > s)
            t++;
    }
    return t;
}
int main(){
    vector<vector<int>> matrix = { { 5, 7, 8, 4 }, { 9, 5, 3, 2 }, { 1, 6, 6, 4 }, { 9, 5, 7, 3 } };
    cout << solve(matrix) << endl;
}

この実装では、全マスについて行と列の合計をそれぞれ計算するため、時間計算量は O(n³) になります。n が小さければ十分実用的ですが、盤面が大きくなる場合は、あらかじめ各行・各列の合計をまとめて計算しておくことで O(n²) まで高速化できます。

入力

{ { 5, 7, 8, 4 }, { 9, 5, 3, 2 }, { 1, 6, 6, 4 }, { 9, 5, 7, 3 } }

出力

6