c - 最长路径: Recursive Backtracking with Constraints in C

Question

我最近被分配了一个问题，归结为找到给定矩阵中的最长路径，其中两个单元格相邻，当且仅当相邻值小于当前单元格。我一直在绞尽脑汁试图弄清楚，所以我将非常感谢任何帮助。然而，正如我所说，这是一项家庭作业，因此非常欢迎建议和提示(但尽量不要让我觉得太容易)。

这是我的代码的最新版本:

#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)。如果有任何其他信息有帮助，请告诉我。任何建议/提示将不胜感激!谢谢。

编辑:原来的问题被颠倒了(即两个单元格是adj，当且仅当相邻单元格具有严格较低的值。这两个问题是等效的，对吧？)

编辑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 -> 

我替换了上面的代码以反射(reflect)这些更改。看起来很接近，但不是完全正确的答案，即路径似乎找到了，但长度不正确。

Answer 1

当前代码的主要问题是引用。
函数执行后需要返回环境。
具体修改示例:

#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);
}