如何在C语言中找到矩阵两点间0路径后将路径0替换为起点值？

现有一段C语言代码可判断给定起点与终点坐标间是否存在由0构成的路径，需求升级为：若找到该路径，将路径上的所有0值替换为起点位置的原始数值。

修改思路 #

• 保存起点原始值：原代码中将起点设为0，需先存储起点的原始数值，作为后续路径替换的目标值。
• 改造DFS实现路径回溯标记：将原DFS仅标记访问状态的逻辑，改为找到终点后在回溯过程中，把当前路径上的0替换为起点值，精准标记有效路径。
• 修正数组初始化错误：原代码中visited数组的维度和循环范围与矩阵实际维度不匹配，需调整为M*N的对应范围。
• 临时修改起点终点状态：为让DFS识别起点终点为路径的一部分，临时将二者设为0，执行完成后可按需恢复原始值。

完整实现代码 #

#include <stdio.h>
#include <stdbool.h>

#define M 4
#define N 5

// 改造后的DFS：找到终点后回溯替换路径值
bool dfs(int adj[][N], int i, int j, bool visited[][N], int targetVal, int dx, int dy) {
    // 边界与合法性判断：越界、非0路径、已访问则返回false
    if (i < 0 || i >= M || j < 0 || j >= N || adj[i][j] != 0 || visited[i][j]) {
        return false;
    }

    visited[i][j] = true;

    // 到达终点，开始回溯替换
    if (i == dx && j == dy) {
        adj[i][j] = targetVal;
        return true;
    }

    // 递归遍历四个方向，只要任一方向找到路径，就替换当前位置并返回true
    if (dfs(adj, i-1, j, visited, targetVal, dx, dy) ||
        dfs(adj, i+1, j, visited, targetVal, dx, dy) ||
        dfs(adj, i, j-1, visited, targetVal, dx, dy) ||
        dfs(adj, i, j+1, visited, targetVal, dx, dy)) {
        adj[i][j] = targetVal;
        return true;
    }

    // 四个方向均无有效路径，取消访问标记（可选，提升逻辑严谨性）
    visited[i][j] = false;
    return false;
}

bool hasPathAndReplace(int adj[][N], int sx, int sy, int dx, int dy) {
    bool visited[M][N];
    int i, j;
    // 初始化visited数组
    for (i = 0; i < M; i++) {
        for (j = 0; j < N; j++) {
            visited[i][j] = false;
        }
    }

    // 保存起点原始值，用于后续路径替换
    int startVal = adj[sx][sy];
    // 临时将起点、终点设为0，确保DFS识别为可通行路径
    int originalEndVal = adj[dx][dy];
    adj[sx][sy] = 0;
    adj[dx][dy] = 0;

    // 执行DFS查找路径并完成替换
    bool hasPath = dfs(adj, sx, sy, visited, startVal, dx, dy);

    // 若需要保留终点原始数值，可取消下方注释恢复
    // adj[dx][dy] = originalEndVal;
    // 起点已被替换为startVal，如需恢复原始值可取消下方注释
    // adj[sx][sy] = startVal;

    return hasPath;
}

// 打印矩阵，直观展示路径替换结果
void printMatrix(int matrix[][N]) {
    printf("修改后的矩阵：\n");
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    // 2D矩阵：1为障碍，0为可通行路径
    int matrix[M][N] = {
        {0, 0, 1, 0, 1},
        {1, 2, 5, 0, 0},
        {0, 0, 2, 0, 1},
        {0, 5, 0, 0, 0}};
  
    int sx = 1, sy = 2, dx = 3, dy = 1;
    printf("查找从(%d,%d)到(%d,%d)的路径：\n", sx, sy, dx, dy);
    
    bool result = hasPathAndReplace(matrix, sx, sy, dx, dy);
    printf("路径存在：%s\n", result ? "是" : "否");

    if (result) {
        printMatrix(matrix);
    }

    return 0;
}

代码说明 #

• 改造后的dfs函数通过回溯机制，在确认找到终点后，反向将路径上的每个0替换为起点的原始值。
• hasPathAndReplace函数负责初始化访问状态、处理起点终点的临时状态修改，最终返回路径是否存在的结果。
• 新增printMatrix函数用于输出修改后的矩阵，直观展示路径替换效果。

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