图的应用，迷宫问题（使用深度优先遍历）

Question

请教一下这串代码应该怎么修改，我的实验结果总是错误

题目：请设计一个程序，输入一个8*8的矩阵，0为通路，1为墙，可走方向：上，下，左，右，左上，左下，右上，右下，起点为左上角，终点为右下角。并判断是否存在一条从起点到终点的通路，如果存在这样的通路，请把通路的坐标输出或者用图形界面进行标记折线路径。

#include<stdio.h>
#define n 8

int dx[8] = { 0,1,1,1,0,-1,-1,-1 };
int dy[8] = { 1,1,0,-1,-1,-1,0,1 };
int maze[n][n] = {
    {0,1,0,0,0,0,1,1},
    {0,0,0,1,0,0,1,0},
    {1,0,1,0,1,0,1,1},
    {1,0,1,0,1,1,0,1},
    {0,1,1,1,1,1,1,0},
    {1,0,0,1,1,0,0,0},
    {1,0,1,0,0,0,1,1},
    {1,0,1,1,0,1,0,0},
};
int visited[n][n] = { 0 };
int tx, ty;

int DFS(int x, int y) {
    if (x == n-1 && y == n-1) {
        visited[x][y] = 1;
        return 1;
    }
    visited[x][y] = 1;
    for (int i = 0; i <8 ; i++) {
        tx = x + dx[i];
        ty = y + dy[i];
        if (tx>=0&&tx<n&&ty>=0&&ty<n&&maze[tx][ty] == 0 && visited[tx][ty] == 0) {
            if (DFS(tx, ty))
                return 1;
        }
    }
    visited[x][y] = 0;
    return 0;
}

void print() {
    if (DFS(0, 0)) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i][j]) {
                    printf("(%d, %d) ", i, j);
                }
            }
        }
    }
    else
        printf("不存在通路");
}

int main() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            visited[i][j] = 0;
        }
    }
    visited[0][0] = 1;
    print();
    return 0;
}

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

您好！我注意到您提供的代码中确实存在一些需要修正的地方。以下是我对您的代码的一些修改建议：

1. 重复标记问题：visited[x][y] = 1; 在 DFS 函数中被重复设置了两次，这可能是一个笔误。应该只设置一次。

2. 路径回溯问题：在 DFS 函数中，当找到一个路径后，您需要确保路径被正确标记。在当前的代码中，当找到一个路径后，visited[x][y] 被设置为 0 来撤销访问标记，这会导致路径无法被正确回溯。

3. 边界条件和通路判断：代码中的边界条件和通路判断逻辑看起来是正确的，但是需要确保 DFS 函数在所有可能的移动方向上都进行了检查。

4. 路径输出问题：print 函数需要修改，以便在找到路径后能够正确地输出路径。

以下是修改后的代码示例：

#include <stdio.h>
#define n 8

int dx[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int dy[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };
int maze[n][n] = {
    // 您的迷宫矩阵
};
int visited[n][n] = { 0 };
int path[n][n]; // 用于存储路径的数组

int DFS(int x, int y) {
    if (x == n - 1 && y == n - 1) {
        path[x][y] = 1; // 标记终点
        return 1;
    }
    if (x < 0 || x >= n || y < 0 || y >= n || maze[x][y] == 1 || visited[x][y] == 1)
        return 0;

    visited[x][y] = 1;
    path[x][y] = 1; // 标记当前位置为路径的一部分

    for (int i = 0; i < 8; i++) {
        int tx = x + dx[i];
        int ty = y + dy[i];
        if (DFS(tx, ty)) {
            return 1;
        }
    }

    visited[x][y] = 0; // 回溯
    path[x][y] = 0; // 清除路径标记
    return 0;
}

void printPath() {
    if (path[n - 1][n - 1]) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (path[i][j]) {
                    printf("(%d, %d) ", i, j);
                }
            }
        }
        printf("\n");
    } else {
        printf("不存在通路\n");
    }
}

int main() {
    DFS(0, 0);
    printPath();
    return 0;
}

请注意，我添加了一个 path 数组来存储路径，并在 DFS 函数中进行了相应的修改。现在，当找到路径时，path 数组将被填充，printPath 函数将使用这个数组来输出路径。

希望这些修改能帮助您解决问题。如果还有其他问题或需要进一步的帮助，请随时告诉我！