বিভিন্ন খরচের একটি ম্যাট্রিক্স দেওয়া আছে। গন্তব্য কক্ষও প্রদত্ত। আমাদের (0, 0) শুরুর কক্ষ থেকে গন্তব্য কক্ষ পর্যন্ত ন্যূনতম খরচের পথ বের করতে হবে।
ম্যাট্রিক্সের প্রতিটি কক্ষ সেই কক্ষ Через যেতে খরচ নির্দেশ করে।
একটি কক্ষ থেকে যেকোনো জায়গায় যাওয়া যায় না। আমরা শুধু ডানে, নিচে বা নিচের ডান ডায়াগোনাল কক্ষে যেতে পারি গন্তব্যে পৌঁছানোর জন্য।
ইনপুট এবং আউটপুট
ইনপুট: খরচ ম্যাট্রিক্স এবং গন্তব্য বিন্দু। এখানে গন্তব্য (2, 2)। 1 2 3 4 8 2 1 5 3 আউটপুট: (0, 0) থেকে গন্তব্যে পৌঁছানোর ন্যূনতম খরচ। ন্যূনতম খরচ ৮।
অ্যালগরিদম
minCostPath(destX, destY, cost)
ইনপুট: গন্তব্যের (x, y) অবস্থান এবং খরচ ম্যাট্রিক্স।
আউটপুট: গন্তব্যে পৌঁছানোর ন্যূনতম খরচ।
শুরু
cost ম্যাট্রিক্সের আকারের totalCost ম্যাট্রিক্স সংজ্ঞায়িত করুন
totalCost[0, 0] = cost[0, 0]
i := 1 থেকে destX পর্যন্ত, করুন
totalCost[i, 0] := totalCost[i-1, 0] + cost[i, 0]
শেষ
j := 1 থেকে destY পর্যন্ত, করুন
totalCost[0, j] := totalCost[0, j-1] + cost[0, j]
শেষ
(1, 1) থেকে (destX, destY) পর্যন্ত সকল অবস্থান (i, j) জন্য, করুন
totalCost[i, j] := totalCost[i-1, j-1], totalCost[i-1, j] এবং totalCost[i, j-1] + cost[i,j] এর মধ্যে ন্যূনতম
শেষ
totalCost[destX, destY] ফেরত দিন
শেষ
উদাহরণ (C++)
#include <iostream>
#define ROW 3
#define COL 3
using namespace std;
int cost[ROW][COL] = {
{1, 2, 3},
{4, 8, 2},
{1, 5, 3}
};
int min(int a, int b, int c) {
return (a
আউটপুট
Minimum Cost: 8
