C++でn×mグリッドを塗る最小コストを求める方法

はじめに

本記事では、n×mグリッドを塗る際の最小コストを求めるプログラムをC++で実装する方法を解説します。

問題設定は以下の通りです。2つの整数 n と m が与えられ、n×m のグリッドを塗りつぶすことを考えます。このとき、1つのセルを塗るコストは「そのセルに隣接する、すでに塗られたセルの数」に等しいものとします。この条件下で、グリッド全体を塗るための最小コストを計算するのが our タスクです。

考え方

この問題は実はシンプルな数式で解くことができます。グリッドを塗る順序を工夫しても、隣接関係によるコストの合計は一定になるため、以下の式で求められます。

最小コスト = (n - 1) × m + (m - 1) × n

この式の意味を分解してみましょう。

• (n - 1) × m： 縦方向の隣接ペアの数。各列には (n - 1) 個の上下の隣接関係があり、それが m 列分あるためです。
• (m - 1) × n： 横方向の隣接ペアの数。各行には (m - 1) 個の左右の隣接関係があり、それが n 行分あるためです。

つまり、グリッド内のすべての隣接セルのペアを数え上げることで、塗るコストの総和が求まります。

実装例

以下に、上記のロジックを実装したC++プログラムを示します。

#include <bits/stdc++.h>
using namespace std;

// 最小コストを計算する関数
int calc_cost(int n, int m){
    int cost = (n - 1) * m + (m - 1) * n;
    return cost;
}

int main(){
    int n = 4, m = 5;
    cout << calc_cost(n, m);
    return 0;
}

出力結果

31

コードの解説

このプログラムでは、n = 4、m = 5 の場合を例に計算しています。

• 縦方向の隣接ペア：(4 - 1) × 5 = 15
• 横方向の隣接ペア：(5 - 1) × 4 = 16
• 合計：15 + 16 = 31

したがって、4×5 のグリッドを塗る最小コストは 31 となります。

計算量

このアルゴリズムは数式を1回評価するだけなので、時間計算量は O(1) です。グリッドのサイズが大きくなっても、瞬時に答えを求められる点が大きなメリットです。

まとめ

n×mグリッドを塗る最小コストは、隣接セルのペア数を数えることで (n - 1) × m + (m - 1) × n という定数時間の計算で求められることを解説しました。グリッド系の問題では、このように隣接関係を数式化できるケースが多いため、考え方として覚えておくと役立ちます。