最長路徑：在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）。請讓我知道，如果任何其他信息會有所幫助。任何建議/提示將不勝感激！謝謝。

編輯：原來的問題正好相反（即兩個單元形容詞當且僅當鄰居有一個嚴格的較低值的兩個問題是等價的，對吧？）

編輯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 -> 

我替換上述代碼以反映這些更改。它似乎非常接近，但並不是正確的答案，即似乎找到了路徑，但長度不正確。

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