#include<stdio.h> #include<stdlib.h> int a[100][100];//这个矩阵有几行几列 int dp[100][100]; //表示从矩阵左上角到每个格子的距离 //Min函数：选择出最小值 int Min(int a,int b){ if(a<b){ return a; }else{ return b; } } //第一行或第一列格子的计算 int getMin(int m,int n){ int min; dp[0][0]=a[0][0]; for(int i=1;i<m;i++){ dp[i][0]=a[i][0]+dp[i-1][0]; } for(int i=1;i<n;i++){ dp[0][i]=a[0][i]+dp[0][i-1]; } //其他格子的计算 for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ min=Min(dp[i-1][j],dp[i][j-1]); dp[i][j]=min+a[i][j]; } } return dp[m-1][n-1]; } int main(){ int m,n; scanf("%d%d",&m,&n);//输入矩阵的横列数 for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ scanf("%d",&a[i][j]);//输入矩阵的值 } } printf("%d\n",getMin(m,n)); return 0; }给代码加入输入提示语句，并加上输出路径

可以在代码中加入如下的输入提示语句：

printf("请输入矩阵的行数和列数：");
scanf("%d%d",&m,&n);
printf("请输入矩阵的值：\n");
for(int i=0;i<m;i++){
    for(int j=0;j<n;j++){
        scanf("%d",&a[i][j]);
    }
}

同时，在程序结束时，可以输出最短路径的长度，并加入输出路径的代码：

printf("最短路径的长度为：%d\n",getMin(m,n));
printf("路径为：");
int i=m-1,j=n-1;
while(i>0 || j>0){
    printf("(%d,%d)->",i,j);
    if(i==0){
        j--;
    }else if(j==0){
        i--;
    }else{
        if(dp[i-1][j]<dp[i][j-1]){
            i--;
        }else{
            j--;
        }
    }
}
printf("(0,0)\n");

这样，完整代码如下：

相关问题

函数接口定义： void CreateUDG(AMGraph &G); //创建图，采用邻接矩阵存储 int DFS(AMGraph G, int v);//以v为起点深度优先遍历，求出各顶点值的和作为函数返回值 裁判测试程序样例： #include <stdio.h> #include <stdlib.h> #define MVNum 100 int visited[MVNum]; typedef struct{ int vexs[MVNum]; //顶点向量，各小岛对应积分

好的，根据您提供的函数接口定义，我给出以下代码示例供参考：

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

#define MVNum 100

// 邻接矩阵存储的图结构体
typedef struct {
    int vexs[MVNum];    // 顶点向量，各小岛对应积分
    int arcs[MVNum][MVNum];  // 邻接矩阵，记录各小岛之间的连通情况
    int vexnum, arcnum; // 顶点数和边数
} AMGraph;

// 创建图，采用邻接矩阵存储
void CreateUDG(AMGraph& G) {
    cout << "请输入小岛数和边数:";
    cin >> G.vexnum >> G.arcnum;
    cout << "请输入各小岛对应积分:";
    for (int i = 0; i < G.vexnum; i++) {
        cin >> G.vexs[i];
    }
    // 初始化邻接矩阵
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = 0; j < G.vexnum; j++) {
            G.arcs[i][j] = 0;
        }
    }
    // 建立边
    cout << "请输入各边的起点和终点:";
    int v1, v2;
    for (int i = 0; i < G.arcnum; i++) {
        cin >> v1 >> v2;
        G.arcs[v1][v2] = 1;
        G.arcs[v2][v1] = 1;
    }
}

// 以v为起点深度优先遍历，求出各顶点值的和作为函数返回值
int DFS(AMGraph G, int v) {
    stack<int> s;
    vector<int> path;
    int sum = 0;
    // 初始化visited数组
    for (int i = 0; i < G.vexnum; i++) {
        visited[i] = 0;
    }
    // 从起点开始遍历
    s.push(v);
    visited[v] = 1;
    sum += G.vexs[v];
    path.push_back(v);
    while (!s.empty()) {
        int cur = s.top();
        int flag = 0;
        for (int i = 0; i < G.vexnum; i++) {
            if (G.arcs[cur][i] == 1 && visited[i] == 0) {
                visited[i] = 1;
                s.push(i);
                sum += G.vexs[i];
                path.push_back(i);
                flag = 1;
                break;
            }
        }
        if (flag == 0) {
            s.pop();
        }
    }
    // 输出遍历路径
    cout << "遍历路径为:";
    for (int i = 0; i < path.size(); i++) {
        cout << path[i] << " ";
    }
    cout << endl;
    return sum;
}

int main() {
    AMGraph G;
    CreateUDG(G);
    int sum = DFS(G, 0);
    cout << "闯关成功者共获得 " << sum << " 积分" << endl;
    return 0;
}

上述代码中，我们先定义了一个邻接矩阵存储的图结构体`AMGraph`，然后定义了`CreateUDG`和`DFS`两个函数，分别用于创建图和进行深度优先遍历计算积分。

在`DFS`函数中，我们使用了一个栈`s`来记录遍历路径，使用一个`path`列表来记录最终的遍历路径，使用一个`sum`变量来记录积分总和。我们首先将起点入栈，并将其对应的积分加入总和中，然后开始遍历。

在遍历过程中，首先取出栈顶元素，然后遍历该元素相邻的未访问过的岛屿，将其压入栈中，并将其对应的积分加入总和中。如果当前岛屿没有未访问过的相邻岛屿，说明该岛屿已经被完全遍历过了，我们将其从栈中弹出。

最后，我们将最终遍历路径输出，并返回积分总和。在`main`函数中，我们调用`CreateUDG`函数创建图，调用`DFS`函数进行深度优先遍历，并输出结果。

#include "graph.h" #include <stdio.h> #include <stdlib.h> void CreateAdj(AdjGraph *&G,int A[MAXV][MAXV],int n,int e) //创建图的邻接表 { int i,j; ArcNode *p; G=(AdjGraph *)malloc(sizeof(AdjGraph)); for(i=0;i<n;i++)

这是一个创建图的邻接表的函数实现，其中AdjGraph是图的邻接表结构体，定义如下：

#define MAXV 100   // 最大顶点数
typedef struct ArcNode{   // 边结点
    int adjvex;           // 邻接点
    struct ArcNode *next; // 指向下一个邻接点的指针
}ArcNode;
typedef struct VNode{     // 顶点结点
    int data;             // 顶点的数据
    ArcNode *first;       // 指向第一个邻接点的指针
}VNode, AdjList[MAXV];
typedef struct{           // 邻接表
    AdjList vertices;     // 存放顶点的数组
    int vexnum, arcnum;   // 顶点数和边数
}AdjGraph;

下面是CreateAdj函数的实现：

void CreateAdj(AdjGraph *&G, int A[MAXV][MAXV], int n, int e)
{
    int i, j;
    ArcNode *p;
    G = (AdjGraph *)malloc(sizeof(AdjGraph));  // 分配内存空间
    for(i = 0; i < n; i++)
    {
        G->vertices[i].data = i;  // 初始化顶点的数据
        G->vertices[i].first = NULL;  // 初始化指向第一个邻接点的指针
        for(j = 0; j < n; j++)
        {
            if(A[i][j] != 0)  // 如果顶点i和顶点j之间有边
            {
                p = (ArcNode *)malloc(sizeof(ArcNode));  // 创建边结点
                p->adjvex = j;  // 邻接点为j
                p->next = G->vertices[i].first;  // 将该边结点插入到顶点i的邻接表头部
                G->vertices[i].first = p;
            }
        }
    }
    G->vexnum = n;  // 顶点数为n
    G->arcnum = e;  // 边数为e
}

其中，A[MAXV][MAXV]是一个邻接矩阵，n是顶点数，e是边数。函数的作用是将邻接矩阵转换为邻接表存储法。