Computer >> Máy Tính >  >> Lập trình >> C ++

Đường dẫn chi phí tối thiểu cho phép di chuyển Trái, Phải, Dưới và Lên trong C ++

Giả sử chúng ta có một mảng 2D. Trong đó mỗi ô trong đó có chi phí số đại diện cho chi phí để truy cập qua ô đó, chúng tôi phải tìm đường dẫn từ ô trên cùng bên trái đến ô dưới cùng bên phải mà theo đó tổng chi phí được tiêu thụ là tối thiểu.

Vì vậy, nếu đầu vào giống như

32 10
1
66 13 19
11 14 48 15
số 8
7
10
1
11
14
17
5
12

34
89 12
5
42 21 14
1
10
0
33 11
2
42

21

thì đầu ra sẽ là 340 là (32 + 11 + 14 + 48 + 66 + 13 + 19 + 7 + 34 + 12 + 21 + 42 + 21) =340

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Xác định ô với tham số tọa độ x, y và khoảng cách.
  • Xác định ma trận mảng có kích thước:row x col.
  • điền vào ma trận với inf
  • Xác định một mảng dx có kích thước:4:={- 1, 0, 1, 0}
  • Xác định một dãy dy có kích thước:4:={0, 1, 0, - 1}
  • Xác định một tập hợp ô được gọi là st
  • chèn ô (0, 0, 0) vào st
  • ma trận [0, 0]:=grid [0, 0]
  • while (not st là trống), do -
    • k:=phần tử đầu tiên của st
    • xóa phần tử đầu tiên của st khỏi st
    • để khởi tạo i:=0, khi i <4, cập nhật (tăng i lên 1), thực hiện -
      • x:=k.x + dx [i]
      • y:=k.y + dy [i]
      • nếu không phải isOk (x, y), thì -
        • Bỏ qua phần sau, chuyển sang phần lặp tiếp theo
      • nếu ma trận [x, y]> ma trận [k.x, k.y] + lưới [x, y], thì -
        • nếu ma trận [x, y] không bằng inf, thì -
          • tìm và xóa ô (x, y, ma trận [x, y]) khỏi st
        • ma trận [x, y]:=ma trận [k.x, k.y] + lưới [x, y]
        • chèn ô (x, y, ma trận [x, y]) vào st
  • ma trận trả về [row - 1, col - 1]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

#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);
}

Đầu vào 

{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
};

Đầu ra:

340