帮我用C++和Qt写一个m*n的矩阵最小路径和可视化,要求用格子展示,最小路径采用其它的颜色标记
时间: 2023-12-10 10:43:00 浏览: 318
好的,以下是一个基本的实现:
1. 首先需要定义一个矩阵类来存储矩阵数据和计算最小路径和。
```c++
class Matrix{
public:
Matrix(int rows, int cols);
~Matrix();
void setValue(int i, int j, int value); //设置元素的值
int getValue(int i, int j); //获取元素的值
int getRows(); //获取行数
int getCols(); //获取列数
int getMinPathSum(); //获取最小路径和
QVector<QVector<int>> getMinPath(); //获取最小路径
private:
int m_rows; //行数
int m_cols; //列数
QVector<QVector<int>> m_data; //矩阵数据
QVector<QVector<int>> m_minPathSum; //最小路径和
QVector<QVector<int>> m_minPath; //最小路径
};
```
2. 在实现矩阵类的时候,需要用到动态规划的思想来计算最小路径和。具体方法如下:
```c++
int Matrix::getMinPathSum()
{
//初始化第一行和第一列
for(int i=0; i<m_rows; i++){
m_minPathSum[i][0] = m_data[i][0];
}
for(int j=1; j<m_cols; j++){
m_minPathSum[0][j] = m_data[0][j] + m_minPathSum[0][j-1];
}
//计算其它位置的最小路径和
for(int i=1; i<m_rows; i++){
for(int j=1; j<m_cols; j++){
m_minPathSum[i][j] = m_data[i][j] + std::min(m_minPathSum[i-1][j], m_minPathSum[i][j-1]);
}
}
return m_minPathSum[m_rows-1][m_cols-1];
}
```
3. 计算出最小路径和后,需要再次运用动态规划的思想来计算最小路径。具体方法如下:
```c++
QVector<QVector<int>> Matrix::getMinPath()
{
//初始化最小路径
m_minPath.clear();
for(int i=0; i<m_rows; i++){
QVector<int> row(m_cols, 0);
m_minPath.push_back(row);
}
//从终点开始逆推最小路径
int i = m_rows-1;
int j = m_cols-1;
while(i>=0 && j>=0){
m_minPath[i][j] = 1;
if(i==0 && j==0){
break;
}
else if(i==0){
j--;
}
else if(j==0){
i--;
}
else{
if(m_minPathSum[i-1][j] < m_minPathSum[i][j-1]){
i--;
}
else{
j--;
}
}
}
return m_minPath;
}
```
4. 最后,需要用Qt来实现可视化。具体方法如下:
```c++
QGraphicsScene* scene = new QGraphicsScene(this);
ui->graphicsView->setScene(scene);
//创建格子
const int gridSize = 50;
for(int i=0; i<m_matrix->getRows(); i++){
for(int j=0; j<m_matrix->getCols(); j++){
QGraphicsRectItem* rectItem = scene->addRect(j*gridSize, i*gridSize, gridSize, gridSize);
rectItem->setPen(QPen(Qt::black));
int value = m_matrix->getValue(i, j);
QString text = QString::number(value);
QGraphicsTextItem* textItem = scene->addText(text);
textItem->setPos(j*gridSize+gridSize/2, i*gridSize+gridSize/2);
textItem->setDefaultTextColor(Qt::black);
}
}
//标记最小路径
QVector<QVector<int>> minPath = m_matrix->getMinPath();
for(int i=0; i<m_matrix->getRows(); i++){
for(int j=0; j<m_matrix->getCols(); j++){
if(minPath[i][j]==1){
QGraphicsRectItem* rectItem = scene->addRect(j*gridSize, i*gridSize, gridSize, gridSize);
rectItem->setBrush(QBrush(Qt::red));
}
}
}
```
完整代码如下:
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)