N×N矩阵DFS寻路代码错误排查：路径赋值不符合预期

问题描述 #

• 需求：在N×N矩阵中，检查指定起点与终点间是否存在仅由0构成的路径，若存在则将路径上的0替换为终点位置的数值。
• 当前问题：运行代码后，所有遍历到的0都被替换为起点的数值，而非仅替换有效路径上的0。

错误原因分析 #

• DFS无回溯逻辑，提前修改矩阵：当前DFS访问到0时立即替换为起点数值，且没有回溯步骤，导致所有被遍历到的0（无论是否在有效路径上）都被修改。
• 替换值方向错误：代码用起点数值替换0，但需求是替换为终点的数值。
• 起点终点临时修改冗余：将起点、终点临时设为0的操作，不仅破坏原始数据，还没必要——起点本身如果不是0，本就不属于可通行路径。

修复方案 #

核心修改点 #

1. 改成回溯式DFS：递归探索时先标记临时值，只有找到终点时才保留路径标记，否则恢复为0。
2. 替换值改为终点的数值，而非起点。
3. 优化起点合法性判断：直接判断起点是否为0或终点，避免无效修改。

修复后的完整代码 #

#include <stdio.h>
#include <stdbool.h>
#define N 5

// 回溯式DFS，返回是否找到路径，找到则标记路径
bool dfs(int adj[][N], int i, int j, bool visited[][N], int dx, int dy, int targetVal) {
    // 越界或已访问，直接返回
    if (i < 0 || i >= N || j < 0 || j >= N || visited[i][j]) {
        return false;
    }
    // 到达终点，标记并返回成功
    if (i == dx && j == dy) {
        adj[i][j] = targetVal;
        return true;
    }
    // 非0且不是终点，无法通行
    if (adj[i][j] != 0) {
        return false;
    }

    visited[i][j] = true;
    adj[i][j] = targetVal; // 临时标记

    // 探索四个方向，只要一个方向找到路径就返回true
    bool found = dfs(adj, i-1, j, visited, dx, dy, targetVal) ||
                 dfs(adj, i+1, j, visited, dx, dy, targetVal) ||
                 dfs(adj, i, j-1, visited, dx, dy, targetVal) ||
                 dfs(adj, i, j+1, visited, dx, dy, targetVal);

    // 没找到路径就回溯，恢复为0
    if (!found) {
        adj[i][j] = 0;
    }

    return found;
}

bool hasPathDfs(int adj[][N], int sx, int sy, int dx, int dy) {
    bool visited[N][N];
    int i, j;
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            visited[i][j] = false;
        }
    }

    int targetVal = adj[dx][dy]; // 用终点数值作为替换值
    // 起点不是0且不是终点，直接返回不可达
    if (adj[sx][sy] != 0 && !(sx == dx && sy == dy)) {
        return false;
    }

    bool startIsEnd = (sx == dx && sy == dy);
    if (!startIsEnd) {
        adj[sx][sy] = targetVal;
        visited[sx][sy] = true;
        // 从起点的四个方向开始搜索
        bool found = dfs(adj, sx-1, sy, visited, dx, dy, targetVal) ||
                     dfs(adj, sx+1, sy, visited, dx, dy, targetVal) ||
                     dfs(adj, sx, sy-1, visited, dx, dy, targetVal) ||
                     dfs(adj, sx, sy+1, visited, dx, dy, targetVal);
        // 没找到路径就恢复起点原始值
        if (!found) {
            adj[sx][sy] = 0;
        }
        return found;
    } else {
        // 起点就是终点，直接标记
        adj[sx][sy] = targetVal;
        return true;
    }
}

int main() {
    int matrix[N][N] = {
        {1, 0, 0, 0, 0},
        {2, 3, 0, 3, 1},
        {0, 4, 0, 0, 0},
        {0, 0, 0, 2, 4},
        {5, 0, 0, 0, 5}};
  
    int sx = 0, sy = 0, dx = 1, dy = 4;
    printf("查找从(%d,%d)到(%d,%d)的路径：\n", sx, sy, dx, dy);
    printf("DFS结果：%s\n", hasPathDfs(matrix, sx, sy, dx, dy) ? "存在" : "不存在");

    printf("修改后的矩阵：\n");
    int i,j;
    for(i=0;i<N;i++){
        for(j=0;j<N;j++){
            printf(" %d ",matrix[i][j]);
        }
        printf("\n");
    }
        
    return 0;
}

修复说明 #

• 回溯机制：只有当递归找到终点时，才保留当前位置的标记；否则恢复为0，确保仅有效路径被修改。
• 替换值正确：使用终点的数值替换路径上的0，符合需求。
• 起点处理优化：提前判断起点合法性，避免无效修改原始数据。

内容的提问来源于stack exchange，提问作者alperone12