এই টিউটোরিয়ালে, n×m আকারের একটি গ্রিড দেওয়া থাকে। প্রতিটি সেল রঙ করার খরচ = তার পাশের ইতিমধ্যে রঙ করা সেলের সংখ্যা। পুরো গ্রিড রঙ করার ন্যূনতম খরচ বের করতে হবে।
ফর্মুলা
ন্যূনতম খরচ = (n-1)×m + (m-1)×n
কারণ: প্রতিটি আন্তরিক প্রান্ত (edge) একবারই গণনা হবে।
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
