समस्या विवरण
मान लीजिए हमारे पास एक 2D सरणी है। जिसके प्रत्येक सेल में संख्या लागत होती है जो उस सेल से गुजरने की लागत को दर्शाती है, हमें शीर्ष-बाएं सेल से नीचे-दाएं सेल तक एक पथ ढूंढना है जिससे कुल खपत लागत न्यूनतम हो।
उदाहरण
| 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 होगा (32 + 11 + 14 + 48 + 66 + 13 + 19 + 7 + 34 + 12 + 21 + 42 + 21) = 340
एल्गोरिदम चरण
- x, y निर्देशांक और दूरी पैरामीटर के साथ सेल परिभाषित करें।
- आकार: पंक्ति x कॉलम की मैट्रिक्स सरणी परिभाषित करें।
- मैट्रिक्स को अनंत से भरें
- आकार 4 के dx सरणी := { -1, 0, 1, 0 } परिभाषित करें
- आकार 4 के dy सरणी := {0, 1, 0, -1 } परिभाषित करें
- सेल नामक एक सेट परिभाषित करें
- सेल(0, 0, 0) को st में डालें
- matrix[0][0] := grid[0][0]
- जब तक st खाली नहीं है:
- k := st का पहला तत्व
- st से पहला तत्व हटाएं
- i := 0 से 3 तक लूप करें:
- x := k.x + dx[i]
- y := k.y + dy[i]
- यदि isOk(x, y) नहीं है, तो अगले पुनरावृत्ति पर जाएं
- यदि matrix[x][y] > matrix[k.x][k.y] + grid[x][y]:
- यदि matrix[x][y] अनंत के बराबर नहीं है, तो st से सेल(x, y, matrix[x][y]) ढूंढें और हटाएं
- matrix[x][y] := matrix[k.x][k.y] + grid[x][y]
- सेल(x, y, matrix[x][y]) को st में डालें
- matrix[row - 1][col - 1] वापस करें
C++ कार्यान्वयन
#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