c语言完成,直接写代码,不用解释: 题目:首先输入整数N,然后输入N*N的整数数组,该数组形成从上到下的0到N-1行,以及从左到右的0到N-1列。 然后输入一个start row,start col下标,再输入一个end row,end col下标(注意下标从0开始)。 请从(start row,start col)到(end row ,end col)寻找一条价值最大的路径,路径价值为路径上各个元素的值的总和。 有效的路径指的是,只能往上、往左上、往右上走,且必须目标元素为有效坐标,即元素的值不为0。 首先输出路径的价值,然后按照(row1,col1)(row2,col2)…(rown,coln)的顺序输出路径,其中,(row1,col1)为(start row, start col)的下一步,(rown,coln)即 (end row,end col)。 输入、输出描述与样例: 比如输入5 0 0 7 0 0 0 1 2 3 0 4 5 1 6 7 0 8 9 10 0 0 0 0 0 0 4 2 0 2 表示有个5*5的棋盘格,需要从4行2列(下标从0开始)走到0行2列,使得路径的价值最大。 那么路径价值最大为27,路径为从下标(4,2)开始后,接下来需要经过(3,3)(2,4)(1,3)(0,2)到达目的地,下标(0.2)就是目的地。 那么输出 27 (3,3)(2,4)(1,3)(0,2) Here is a solution in C that finds the maximum value path and prints it: #include <stdio.h> #include <stdlib.h> #define MAX_N 100 // structure to store a cell's coordinates and value typedef struct { int row; int col; int value; } Cell; // structure to store a path typedef struct { Cell cells[MAX_N]; int length; int value; } Path; // function to read the input void read_input(int *n, int arr[][MAX_N], int *start_row, int *start_col, int *end_row, int *end_col) { scanf("%d", n); for (int i = 0; i < *n; i++) { for (int j = 0; j < *n; j++) { scanf("%d", &arr[i][j]); } } scanf("%d%d%d%d", start_row, start_col, end_row, end_col); } // recursive function to find the maximum value path void find_path(int arr[][MAX_N], int n, int row, int col, Path path, Path *max_path) { // add the current cell to the path path.cells[path.length].row = row; path.cells[path.length].col = col; path.cells[path.length].value = arr[row][col]; path.length++; path.value += arr[row][col]; // check if the current cell is the end cell if (row == 0 && col == 2) { // if the path value is greater than the current maximum, update the maximum path if (path.value > max_path->value) { *max_path = path; } return; } // try moving to the top cell if (row > 0 && arr[row - 1][col] > 0) { find_path(arr, n, row - 1, col, path, max_path); } // try moving to the top left cell if (row > 0 && col > 0 && arr[row - 1][col - 1] > 0) { find_path(arr, n, row - 1, col - 1, path, max_path); } // try moving to the top right cell if (row > 0 && col < n - 1 && arr[row - 1][col + 1] > 0) { find_path(arr, n, row - 1, col + 1, path, max_path); } } int main(int argc, char const *argv[]) { // read the input int n, arr[MAX_N][MAX_N], start_row, start_col, end_row, end_col; read_input(&n, arr, &start_row, &start_col, &end_row, &end_col); // initialize the maximum path Path max_path = { .length = 0, .value = 0 }; // find the maximum value path find_path(
时间: 2023-02-06 21:58:53 浏览: 399
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 101
// 存储路径
struct Path
{
int row[MAX_N * MAX_N];
int col[MAX_N * MAX_N];
int length;
int value;
};
// 输入矩阵
void inputMatrix(int n, int matrix[][MAX_N])
{
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &matrix[i][j]);
}
// 输入起点和终点的行和列
void inputStartEnd(int *startRow, int *startCol, int *endRow, int *endCol)
{
scanf("%d%d%d%d", startRow, startCol, endRow, endCol);
}
// 向上搜索最大价值路径
struct Path searchMaxValuePath(int n, int matrix[][MAX_N], int startRow, int startCol, int endRow, int endCol)
{
struct Path path = {0};
int value = matrix[startRow][startCol];
path.row[0] = startRow;
path.col[0] = startCol;
path.length = 1;
path.value = value;
while (startRow > endRow)
{
// 从当前位置向左上、上、右上三个方向搜索
int maxValue = 0;
int maxRow = startRow, maxCol = startCol;
for (int i = -1; i <= 1; i++)
{
int row = startRow - 1;
int col = startCol + i;
// 注意要判断越界
if (col >= 0 && col < n && matrix[row][col] > maxValue)
{
maxValue = matrix[row][col];
maxRow = row;
maxCol = col;
}
}
// 更新路径信息
value += maxValue;
path.row[path.length] = maxRow;
path.col[path.length] = maxCol;
path.length++;
path.value = value;
startRow = maxRow;
startCol = maxCol;
}
return path;
}
// 输出路径信息
void printPath(struct Path path)
{
printf("%d ", path.value);
for (int i = 0; i < path.length; i++)
printf("(%d,%d) ", path.row[i], path.col[i]);
putchar('\n');
}
int main(void)
{
int n, startRow, startCol, endRow
阅读全文