ধরুন আমাদের একটি 2D অ্যারে আছে। যেখানে প্রতিটি কক্ষের সংখ্যা খরচ থাকে যা সেই কক্ষের মাধ্যমে পরিদর্শন করার খরচকে উপস্থাপন করে, আমাদের উপরের-বাম কক্ষ থেকে নীচে-ডান কক্ষে একটি পথ খুঁজে বের করতে হবে যার দ্বারা মোট খরচ সর্বনিম্ন।
সুতরাং, যদি ইনপুট মত হয়
32 | 10 1 | 66 | 13 | 19 |
11 | 14 | 48 | 15 8 | 7 |
10 1 | 11 14 | 17 5 | 12 | 34 |
89 | 12 5 | 42 | 21 | 14 1 |
10 0 | 33 | 11 2 | 42 | 21 |
তাহলে আউটপুট 340 হবে (32 + 11 + 14 + 48 + 66 + 13 + 19 + 7 + 34 + 12 + 21 + 42 + 21) =340
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- x, y স্থানাঙ্ক এবং দূরত্বের প্যারামিটার দিয়ে ঘরকে সংজ্ঞায়িত করুন।
- আকারের একটি অ্যারে ম্যাট্রিক্স সংজ্ঞায়িত করুন:সারি x কল।
- inf দিয়ে ম্যাট্রিক্স পূরণ করুন
- আকারের একটি অ্যারে dx সংজ্ঞায়িত করুন:4 :={ - 1, 0, 1, 0
- আকারের একটি অ্যারে dy সংজ্ঞায়িত করুন:4 :={0, 1, 0, - 1
- স্ট নামক কোষের একটি সেট সংজ্ঞায়িত করুন
- স্ট-এ সেল (0, 0, 0) ঢোকান
- ম্যাট্রিক্স[0, 0] :=গ্রিড[0, 0]
- যখন (st খালি নয়), −
- করুন
- k :=st এর প্রথম উপাদান
- st থেকে st-এর প্রথম উপাদান মুছুন
- আরম্ভ করার জন্য i :=0, যখন i <4, আপডেট করুন (i 1 দ্বারা বৃদ্ধি করুন), −
- করুন
- x :=k.x + dx[i]
- y :=k.y + dy[i]
- যদি না হয় ঠিক আছে(x, y), তাহলে −
- নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তিতে যান
- যদি ম্যাট্রিক্স[x, y]> ম্যাট্রিক্স[k.x, k.y] + গ্রিড[x, y] হয়, তাহলে −
- যদি ম্যাট্রিক্স[x, y] inf এর সমান না হয়, তাহলে −
- st থেকে সেল (x, y, matrix[x, y]) খুঁজুন এবং মুছুন
- ম্যাট্রিক্স[x, y] :=ম্যাট্রিক্স[k.x, k.y] + গ্রিড[x, y]
- st-এ সেল (x, y, ম্যাট্রিক্স[x, y]) ঢোকান
- যদি ম্যাট্রিক্স[x, y] inf এর সমান না হয়, তাহলে −
- রিটার্ন ম্যাট্রিক্স[সারি - 1, কল - 1]
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h> using namespace std; #define ROW 5 #define COL 5 class cell { public: int x, y; int distance; cell(int x, int y, int distance) : x(x), y(y), distance(distance) {} }; bool operator<(const cell& a, const cell& b) { if (a.distance == b.distance) { if (a.x != b.x) return (a.x < b.x); else return (a.y < b.y); } return (a.distance < b.distance); } bool isOk(int i, int j) { return (i >= 0 && i < COL && j >= 0 && j < ROW); } int solve(int grid[ROW][COL], int row, int col) { int matrix[row][col]; for (int i = 0; i < row; i++) for (int j = 0; j < col; j++) matrix[i][j] = INT_MAX; int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; set<cell> st; st.insert(cell(0, 0, 0)); matrix[0][0] = grid[0][0]; while (!st.empty()) { cell k = *st.begin(); st.erase(st.begin()); for (int i = 0; i < 4; i++) { int x = k.x + dx[i]; int y = k.y + dy[i]; if (!isOk(x, y)) continue; if (matrix[x][y] > matrix[k.x][k.y] + grid[x][y]){ if (matrix[x][y] != INT_MAX) st.erase(st.find(cell(x, y, matrix[x][y]))); matrix[x][y] = matrix[k.x][k.y] + grid[x][y]; st.insert(cell(x, y, matrix[x][y])); } } } return matrix[row - 1][col - 1]; } int main() { int grid[ROW][COL] = { 32, 101, 66, 13, 19, 11, 14, 48, 158, 7, 101, 114, 175, 12, 34, 89, 126, 42, 21, 141, 100, 33, 112, 42, 21 }; cout << solve(grid, ROW, COL); }
ইনপুট
{32, 101, 66, 13, 19, 11, 14, 48, 158, 7, 101, 114, 175, 12, 34, 89, 126, 42, 21, 141, 100, 33, 112, 42, 21 };
আউটপুট:
340