C++ 中允許向左、向右、向下和向上移動的最小成本路徑

假設我們有一個二維陣列。其中每個單元格包含一個表示訪問該單元格的成本的數字成本，我們必須找到從左上角單元格到右下角單元格的路徑，使消耗的總成本最小。

因此，如果輸入類似於

那麼輸出將為 340，因為 (32 + 11 + 14 + 48 + 66 + 13 + 19 + 7 + 34 + 12 + 21 + 42 + 21) = 340

為了解決這個問題，我們將遵循以下步驟：

• 定義具有 x、y 座標和距離引數的單元格。
• 定義大小為：行 x 列的陣列矩陣。
• 用 inf 填充矩陣
• 定義大小為：4 的陣列 dx := { - 1, 0, 1, 0}
• 定義大小為：4 的陣列 dy := {0, 1, 0, - 1}
• 定義一組稱為 st 的單元格
• 將單元格(0, 0, 0) 插入 st
• matrix[0, 0] := grid[0, 0]
• 當 (st 不為空) 時，執行：
  • k := st 的第一個元素
  • 從 st 中刪除 st 的第一個元素
  • 初始化 i := 0，當 i < 4 時，更新 (i 增加 1)，執行：
    • 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] 不等於 inf，則：
        • 從 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]

示例

讓我們看看以下實現以更好地理解：

即時演示

#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

Arnab Chakraborty

更新於： 2020-08-27

378 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始