【C++】チェス盤を2つに分断せずに切れる最大カット数の求め方

概要

A × B のマス目からなるチェス盤が与えられたとき、「盤面を2つに分断してしまわない」という条件を満たす範囲で、最大で何回のカット(切り込み)を入れられるかを求めるのが本記事のテーマです。

一見すると単純なパズルのように見えますが、盤面のつながりを保ちながらどこまで切り進められるかを考える、幾何学およびグラフ理論の観点からも興味深い問題です。

入出力の例

具体的な入力と出力の例は以下の通りです。

入力

A = 2, B = 4

出力

最大カット数 = 3

入力

A = 2, B = 2

出力

最大カット数 = 1

考え方

• A = 2、B = 2 の場合、カットできるのは1回だけです(赤線部分)。ここにもう1回切り込みを入れると、盤面は2つのピースに分かれてしまいます。

• A = 2、B = 4 の場合は、3回のカットが可能です(赤線部分)。ここにさらに1回切り込みを加えると、やはり盤面は2つに分断されます。

これらの結果から、次の一般式が導けます。

最大カット数 = (A − 1) × (B − 1)

直感的に説明すると、切り込みを重ねても盤面全体が「ひとつながりの状態」を保てる限りはカットを続けられますが、それ以上切ると必ず盤が分断されるという限界が (A−1)×(B−1) 回になるのです。

C++での実装例

上記の考え方をC++で実装すると、以下のようになります。

// 上記アプローチのC++実装
#include <bits/stdc++.h>
using namespace std;
// 最大カット数を計算する関数
int numberOfCuts1(int A, int B){
    int result1 = 0;
    result1 = (A - 1) * (B - 1);
    return result1;
}
// ドライバーコード
int main(){
    int A = 4, B = 4;
    // 関数を呼び出す
    int Cuts = numberOfCuts1(A, B);
    cout << "Maximum cuts = " << Cuts;
    return 0;
}

出力

Maximum cuts = 9

4 × 4 のチェス盤の場合、(4−1) × (4−1) = 9 となり、盤面を分断することなく最大9回のカットが可能であることが確認できます。計算量は掛け算1回のみのため、非常に効率的なO(1)アルゴリズムと言えます。