C ++中允许的向左，向右，向下和向上移动的最小成本路径
假设我们有一个二维数组。如果每个单元格由数字成本组成，代表通过该单元格访问的成本，我们必须找到一条从左上角到右下角的路径，由此消耗的总成本最小。
所以，如果输入像
1
8
1
14
5
5
1
0
2
那么输出将为340，因为（32+11+14+48+66+13+19+7+34+12+21+42+21）=340
为了解决这个问题，我们将遵循以下步骤-
使用x，y坐标和距离参数定义单元格。
定义大小为：行xcol的数组矩阵。
用inf填充矩阵
定义大小为dx的数组dx：4：={-1，0，1，0}
定义大小为4的数组dy：=：{0，1，0，-1}
定义一组称为st的单元格
将cell(0,0,0)插入st
矩阵[0，0]：=网格[0，0]
虽然（不是st为空），请-
x：=kx+dx[i]
y：=ky+dy[i]
如果不是isOk(x,y)，则-
如果matrix[x，y]>matrix[kx，ky]+grid[x，y]，则-
忽略以下部分，跳至下一个迭代
从st查找并删除单元格（x，y，matrix[x，y]）
如果matrix[x，y]不等于inf，则-
矩阵[x，y]：=矩阵[kx，ky]+网格[x，y]
将cell（x，y，matrix[x，y]）插入st
k：=st的第一个元素
从st删除st的第一个元素
对于初始化i：=0，当i<4时，更新（将i增加1），请执行-
返回矩阵[行-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