最长路径：C 中具有约束的递归回溯
Longest Path: Recursive Backtracking with Constraints in C
我最近被分配了一个问题，归结为寻找给定矩阵中的最长路径，其中两个单元格相邻，前提是相邻值小于当前单元格。我一直在努力弄清楚，所以我将非常感谢任何帮助。但是，正如我所说，这是一项家庭作业，因此非常欢迎提出建议和提示（但尽量不要让我觉得太容易）。
这是我的代码的最新版本：
#include <stdio.h>
int isValid(int i, int j, int rows, int cols) {
if (i < 0 || i >= rows || j < 0 || j >= cols)
return 0;
return 1;
}
void printpath(int path[1000][2]) {
int i = 0;
while (path[i][0] != -1) {
printf("(%d, %d) ", path[i][0], path[i][1]);
i++;
}
}
void print_array_path(int path[1000][2], int array[100][100]) {
int i = 0;
while (path[i][0] != -1) {
printf("%d -> ", array[path[i][0]][path[i][1]]);
i++;
}
}
int path_length(int path[1000][2]) {
int i = 0, s = 0;
while ( path[i][0] != -1) {
s++;
i++;
}
return s-1;
}
void add_path(int path[1000][2], int u, int v) {
int i = 0;
while (path[i][0] != -1) {
i++;
}
path[i][0] = u; // row
path[i][1] = v; // column
}
int last_i(int path[1000][2], int s) {
int v;
v = path[s][0];
//path[i-2][0] = -1;
return v;
}
int last_j(int path[1000][2], int s) {
int u;
u = path[s][1];
//path[i-2][1] = -1;
return u;
}
int c1[4] = {1, 0, -1, 0};
int c2[4] = {0, 1, 0, -1};
int dfs(int visited[100][100], int array[100][100], int i, int j, int rows, int cols, int path[1000][2], int length) {
// 1. Take the current visited, along with the previous vertex, to create a unique
// list of visited vertices.
// 2. For every direction, check if it is valid. If valid, do dfs(visited, current, choice)
// 3. If all four directions are checked, with no valid choice, report the solution.
int s;
for (s=0; s<4; s++) {
if ( isValid(i+c1[s], j+c2[s], rows, cols) && !(visited[i+c1[s]][j+c2[s]]) && (array[i][j] < array[i+c1[s]][j+c2[s]]) ) {
// TODO visited.add(current)
visited[i][j] = 1;
add_path(path, i+c1[s], j+c2[s]);
//printf("%d -> ", array[i+c1[s]][j+c2[s]]);
//printpath(path);
length += 1;
dfs( visited, array, i+c1[s], j+c2[s], rows, cols, path, length);
} else if (s==3) {
//visited[i+c1[s]][j+c2[s]] = 0;
//printf("end at %d, %d\n", i, j);
if ( (last_i(path, i) == i) && (last_i(path, j) == j) ){
printf("%d ", length);
print_array_path(path, array);
printf("\n");
continue;
}
length -= 1;
dfs(visited, array, last_i(path, i-1), last_j(path, i-1), rows, cols, path, length);
return path[i][0];
}
}
}
int main() {
int array[100][100];
int rows, columns;
scanf("%d", &rows);
scanf("%d", &columns);
int i, j;
for (i = 0; i < rows; i++) {
for (j = 0; j < columns; j++) {
scanf("%d", &array[i][j]);
}
}
for (i = 0; i < rows; i++) {
for (j = 0; j < columns; j++) {
printf("%d ", array[i][j]);
}
printf("\n");
}
int visited[100][100];
for (i=0; i<rows; i++) {
for (j=0; j<columns; j++) {
visited[i][j] = 0;
}
}
int path[1000][2];
for (i=0; i<1000; i++) {
for (j=0; j<2; j++) {
path[i][j] = -1;
}
}
path[0][1] = 0;
path[0][0] = 0;
int length = 0;
dfs(visited, array, 0, 0, rows, columns, path, length);
}
基本上，它首先收集一个输入矩阵，并从第一个单元格开始（一旦我使整个事情正常工作，它将遍历每个单元格），调用搜索功能，检查是否有相邻单元格有效，然后再次调用搜索。如果检查了所有四个方向，它会回溯。当前路径正在列表 path 中跟踪。我的问题似乎主要出在回溯部分。但是，我不确定如何前进。这段代码目前几乎无法编译，因为我一直在尝试很多不同的东西。在这一点上，我想屏住呼吸，真正理解我要做什么。
早些时候，我尝试生成一个邻接列表，并从中构建路径，但回溯选项似乎更有希望。典型的输入如下所示：
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
表达一个5x5的矩阵。预期输出为 25（25->24-> ... 2->1）。如果有任何其他信息有帮助，请告诉我。任何建议/提示将不胜感激！谢谢
编辑：原来的问题被颠倒了（即两个单元格被调整，如果邻居有一个严格较低的值。这两个问题是等价的，对吧？）
编辑 2：我对代码做了一些修改，我想我更接近了。它现在给出这个输出：
3 1 -> 16 -> 17 -> 24 -> 25 ->
3 1 -> 16 -> 17 -> 24 -> 25 ->
4 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 ->
9 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 ->
10 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 ->
8 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 ->
17 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 ->
20 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 ->
21 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 ->
21 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 ->
19 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
19 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
13 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
12 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
11 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
9 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
8 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
7 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
8 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
7 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
5 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
4 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
2 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
1 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
我替换了上面的代码以反映这些更改。看起来很接近，但不是很正确的答案，即路径似乎找到了，但长度不正确。
当前代码的主要问题是trackback。
执行函数后需要return环境
具体修改示例：
#include <stdio.h>
#include <stdbool.h>
#define MAX_LEN 1000
#define SIZE 100
#define EOP -1 //End Of Path
typedef struct pos {
int r, c;//rows, columns
} Pos;
Pos EPOS = { EOP, EOP};
bool isValidPos(Pos pos, int rows, int cols) {
return 0 <= pos.r && pos.r < rows && 0 <= pos.c && pos.c < cols;
}
bool isVisited(Pos pos, bool visited[SIZE][SIZE]){
return visited[pos.r][pos.c];
}
/* unused
void printPos(Pos pos){
printf("(%d, %d)", pos.r, pos.c);
}
void printpath(Pos path[]){
while(path->r != EOP)
printPos(*path++);
}
int path_length(Pos path[]) {
int i = 0;
while((path++)->r != EOP)
++i;
return i;
}
void add_path(Pos path[], Pos pos) {
while (path->r != EOP)
++path;
*path = pos;
path[1] = EPOS;
}
*/
int valueOf(Pos pos, int array[SIZE][SIZE]){
return array[pos.r][pos.c];
}
void print_path(Pos path[], int array[SIZE][SIZE]){
while(path->r != EOP)
printf("%d -> ", valueOf(*path++, array));
}
const Pos rpos[] = {{1,0},{0,1},{-1,0},{0,-1}};//relative position
void dfs(bool visited[SIZE][SIZE], int array[SIZE][SIZE], Pos pos, int rows, int cols, Pos path[], int length){
visited[pos.r][pos.c] = true;
int value = valueOf(pos, array);
bool CantAddPath = true;
for (int s = 0; s < sizeof(rpos)/sizeof(*rpos); s++){
Pos movePos = { .r = pos.r + rpos[s].r, .c = pos.c + rpos[s].c};
if(!isValidPos(movePos, rows, cols) || isVisited(movePos, visited) || value >= valueOf(movePos, array))
continue;
CantAddPath = false;
path[length++] = pos;//add_path(path, pos);length++;
dfs(visited, array, movePos, rows, cols, path, length);
path[--length] = EPOS;
}
if(CantAddPath){
printf("%d ", length+1);//+1: current (last) postion
print_path(path, array);
printf("%d\n", value);//value of current (last) position
}
visited[pos.r][pos.c] = false;
}
int main(void) {
int array[SIZE][SIZE];
int rows, columns;
scanf("%d", &rows);
scanf("%d", &columns);
int i, j;
for(i = 0; i < rows; i++)
for(j = 0; j < columns; j++)
scanf("%d", &array[i][j]);
for(i = 0; i < rows; i++){
for(j = 0; j < columns; j++)
printf("%2d ", array[i][j]);
printf("\n");
}
bool visited[SIZE][SIZE] = {{ false }};
Pos path[MAX_LEN];
for (i = 0; i < MAX_LEN; i++){
path[i] = EPOS;
}
Pos start = { 0, 0 };
//path[0] = start;//Mismatch with `int length = 0;`
int length = 0;
dfs(visited, array, start, rows, columns, path, length);
}
我最近被分配了一个问题，归结为寻找给定矩阵中的最长路径，其中两个单元格相邻，前提是相邻值小于当前单元格。我一直在努力弄清楚，所以我将非常感谢任何帮助。但是，正如我所说，这是一项家庭作业，因此非常欢迎提出建议和提示（但尽量不要让我觉得太容易）。
这是我的代码的最新版本：
#include <stdio.h>
int isValid(int i, int j, int rows, int cols) {
if (i < 0 || i >= rows || j < 0 || j >= cols)
return 0;
return 1;
}
void printpath(int path[1000][2]) {
int i = 0;
while (path[i][0] != -1) {
printf("(%d, %d) ", path[i][0], path[i][1]);
i++;
}
}
void print_array_path(int path[1000][2], int array[100][100]) {
int i = 0;
while (path[i][0] != -1) {
printf("%d -> ", array[path[i][0]][path[i][1]]);
i++;
}
}
int path_length(int path[1000][2]) {
int i = 0, s = 0;
while ( path[i][0] != -1) {
s++;
i++;
}
return s-1;
}
void add_path(int path[1000][2], int u, int v) {
int i = 0;
while (path[i][0] != -1) {
i++;
}
path[i][0] = u; // row
path[i][1] = v; // column
}
int last_i(int path[1000][2], int s) {
int v;
v = path[s][0];
//path[i-2][0] = -1;
return v;
}
int last_j(int path[1000][2], int s) {
int u;
u = path[s][1];
//path[i-2][1] = -1;
return u;
}
int c1[4] = {1, 0, -1, 0};
int c2[4] = {0, 1, 0, -1};
int dfs(int visited[100][100], int array[100][100], int i, int j, int rows, int cols, int path[1000][2], int length) {
// 1. Take the current visited, along with the previous vertex, to create a unique
// list of visited vertices.
// 2. For every direction, check if it is valid. If valid, do dfs(visited, current, choice)
// 3. If all four directions are checked, with no valid choice, report the solution.
int s;
for (s=0; s<4; s++) {
if ( isValid(i+c1[s], j+c2[s], rows, cols) && !(visited[i+c1[s]][j+c2[s]]) && (array[i][j] < array[i+c1[s]][j+c2[s]]) ) {
// TODO visited.add(current)
visited[i][j] = 1;
add_path(path, i+c1[s], j+c2[s]);
//printf("%d -> ", array[i+c1[s]][j+c2[s]]);
//printpath(path);
length += 1;
dfs( visited, array, i+c1[s], j+c2[s], rows, cols, path, length);
} else if (s==3) {
//visited[i+c1[s]][j+c2[s]] = 0;
//printf("end at %d, %d\n", i, j);
if ( (last_i(path, i) == i) && (last_i(path, j) == j) ){
printf("%d ", length);
print_array_path(path, array);
printf("\n");
continue;
}
length -= 1;
dfs(visited, array, last_i(path, i-1), last_j(path, i-1), rows, cols, path, length);
return path[i][0];
}
}
}
int main() {
int array[100][100];
int rows, columns;
scanf("%d", &rows);
scanf("%d", &columns);
int i, j;
for (i = 0; i < rows; i++) {
for (j = 0; j < columns; j++) {
scanf("%d", &array[i][j]);
}
}
for (i = 0; i < rows; i++) {
for (j = 0; j < columns; j++) {
printf("%d ", array[i][j]);
}
printf("\n");
}
int visited[100][100];
for (i=0; i<rows; i++) {
for (j=0; j<columns; j++) {
visited[i][j] = 0;
}
}
int path[1000][2];
for (i=0; i<1000; i++) {
for (j=0; j<2; j++) {
path[i][j] = -1;
}
}
path[0][1] = 0;
path[0][0] = 0;
int length = 0;
dfs(visited, array, 0, 0, rows, columns, path, length);
}
基本上，它首先收集一个输入矩阵，并从第一个单元格开始（一旦我使整个事情正常工作，它将遍历每个单元格），调用搜索功能，检查是否有相邻单元格有效，然后再次调用搜索。如果检查了所有四个方向，它会回溯。当前路径正在列表 path 中跟踪。我的问题似乎主要出在回溯部分。但是，我不确定如何前进。这段代码目前几乎无法编译，因为我一直在尝试很多不同的东西。在这一点上，我想屏住呼吸，真正理解我要做什么。
早些时候，我尝试生成一个邻接列表，并从中构建路径，但回溯选项似乎更有希望。典型的输入如下所示：
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
表达一个5x5的矩阵。预期输出为 25（25->24-> ... 2->1）。如果有任何其他信息有帮助，请告诉我。任何建议/提示将不胜感激！谢谢
编辑：原来的问题被颠倒了（即两个单元格被调整，如果邻居有一个严格较低的值。这两个问题是等价的，对吧？）
编辑 2：我对代码做了一些修改，我想我更接近了。它现在给出这个输出：
3 1 -> 16 -> 17 -> 24 -> 25 ->
3 1 -> 16 -> 17 -> 24 -> 25 ->
4 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 ->
9 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 ->
10 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 ->
8 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 ->
17 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 ->
20 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 ->
21 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 ->
21 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 ->
19 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
19 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
13 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
12 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
11 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
9 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
8 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
7 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
8 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
7 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
5 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
4 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
2 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
1 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
我替换了上面的代码以反映这些更改。看起来很接近，但不是很正确的答案，即路径似乎找到了，但长度不正确。
当前代码的主要问题是trackback。
执行函数后需要return环境
具体修改示例：
#include <stdio.h>
#include <stdbool.h>
#define MAX_LEN 1000
#define SIZE 100
#define EOP -1 //End Of Path
typedef struct pos {
int r, c;//rows, columns
} Pos;
Pos EPOS = { EOP, EOP};
bool isValidPos(Pos pos, int rows, int cols) {
return 0 <= pos.r && pos.r < rows && 0 <= pos.c && pos.c < cols;
}
bool isVisited(Pos pos, bool visited[SIZE][SIZE]){
return visited[pos.r][pos.c];
}
/* unused
void printPos(Pos pos){
printf("(%d, %d)", pos.r, pos.c);
}
void printpath(Pos path[]){
while(path->r != EOP)
printPos(*path++);
}
int path_length(Pos path[]) {
int i = 0;
while((path++)->r != EOP)
++i;
return i;
}
void add_path(Pos path[], Pos pos) {
while (path->r != EOP)
++path;
*path = pos;
path[1] = EPOS;
}
*/
int valueOf(Pos pos, int array[SIZE][SIZE]){
return array[pos.r][pos.c];
}
void print_path(Pos path[], int array[SIZE][SIZE]){
while(path->r != EOP)
printf("%d -> ", valueOf(*path++, array));
}
const Pos rpos[] = {{1,0},{0,1},{-1,0},{0,-1}};//relative position
void dfs(bool visited[SIZE][SIZE], int array[SIZE][SIZE], Pos pos, int rows, int cols, Pos path[], int length){
visited[pos.r][pos.c] = true;
int value = valueOf(pos, array);
bool CantAddPath = true;
for (int s = 0; s < sizeof(rpos)/sizeof(*rpos); s++){
Pos movePos = { .r = pos.r + rpos[s].r, .c = pos.c + rpos[s].c};
if(!isValidPos(movePos, rows, cols) || isVisited(movePos, visited) || value >= valueOf(movePos, array))
continue;
CantAddPath = false;
path[length++] = pos;//add_path(path, pos);length++;
dfs(visited, array, movePos, rows, cols, path, length);
path[--length] = EPOS;
}
if(CantAddPath){
printf("%d ", length+1);//+1: current (last) postion
print_path(path, array);
printf("%d\n", value);//value of current (last) position
}
visited[pos.r][pos.c] = false;
}
int main(void) {
int array[SIZE][SIZE];
int rows, columns;
scanf("%d", &rows);
scanf("%d", &columns);
int i, j;
for(i = 0; i < rows; i++)
for(j = 0; j < columns; j++)
scanf("%d", &array[i][j]);
for(i = 0; i < rows; i++){
for(j = 0; j < columns; j++)
printf("%2d ", array[i][j]);
printf("\n");
}
bool visited[SIZE][SIZE] = {{ false }};
Pos path[MAX_LEN];
for (i = 0; i < MAX_LEN; i++){
path[i] = EPOS;
}
Pos start = { 0, 0 };
//path[0] = start;//Mismatch with `int length = 0;`
int length = 0;
dfs(visited, array, start, rows, columns, path, length);
}