C语言DFS迷宫最短路径算法方向优先级异常问题求助

问题背景 #

开发基于DFS的C语言迷宫求解程序，需求为：

• 找出2D网格中从起点S到终点E的最短路径
• 路径选择需遵循右、左、上、下的方向优先级
  当前存在问题：

1. 路径优先向下移动，修改方向向量后无改善
2. 将最短路径判断条件从length < minimum改为length <= minimum后，两个测试案例输出均异常

测试案例与异常表现 #

测试案例1（15x13迷宫） #

输入：

15 13
###############
#S...........##
#............##
#...........E##
###############
###############
###############
###############
###############
###############
###############
###############
###############

异常输出（路径优先向下）：

###############
#S...........##
#x...........##
#xxxxxxxxxxxE##
###############
###############
###############
###############
###############
###############
###############
###############
###############

修改判断条件为length <= minimum后的异常输出：

###############
#Sxxxxxxxxxxx##
#...........x##
#...........E##
###############
###############
###############
###############
###############
###############
###############
###############
###############

测试案例2（5x5迷宫） #

输入：

5 5
#E..#
#...#
#...#
##...
####S

预期输出：

#Exx#
#..x#
#..x#
##.xx
####S

修改判断条件后的异常输出：

####S
#E..#
#x..#
#xx.#
##xxx
####S

问题根源分析 #

1. 方向向量定义错误：原代码的方向向量未匹配「右、左、上、下」的优先级，且混淆了行（x）和列（y）的坐标变化逻辑
2. 最短路径记录逻辑缺陷：原代码在DFS过程中实时修改网格，当存在多条等长最短路径时，后遍历到的路径会覆盖先找到的路径，导致优先级失效；仅用length < minimum时，仅保留第一条找到的最短路径，但因方向向量错误导致路径不符合预期
3. 坐标索引混淆：输入的行列顺序（先列后行）与代码中grid的访问逻辑未完全对应，进一步加剧方向判断错误

修复方案 #

1. 修正方向向量 #

按照「右、左、上、下」的优先级，正确定义行（x）和列（y）的变化：

• 右：列+1，行不变 → moveX=0, moveY=1
• 左：列-1，行不变 → moveX=0, moveY=-1
• 上：行-1，列不变 → moveX=-1, moveY=0
• 下：行+1，列不变 → moveX=1, moveY=0

对应的代码：

int moveX[4] = {0, 0, -1, 1}; // 行变化：右/左不变，上减1，下加1
int moveY[4] = {1, -1, 0, 0}; // 列变化：右加1，左减1，上/下不变

2. 重构最短路径搜索逻辑 #

将搜索分为两步，避免实时修改网格导致的路径覆盖：

• 第一步：仅计算最短路径长度minimum，不修改网格
• 第二步：重置visited数组，再次DFS，仅寻找长度等于minimum的路径，按方向优先级遍历，找到第一条符合条件的路径后标记并终止搜索

3. 修正路径标记逻辑 #

新增一个单独的数组记录最终路径，避免在DFS过程中反复修改原始网格，确保只保留符合优先级的最短路径。

修改后的完整代码 #

#include <stdio.h>
#include <string.h>

char grid[15][15];
int visited[15][15];
int path[15][15]; // 记录最终路径
int x, y;
// 方向优先级：右、左、上、下
int moveX[4] = {0, 0, -1, 1};
int moveY[4] = {1, -1, 0, 0};
int length = 0;
int startX, startY, endX, endY;
int minimum = 2147483647;
int found = 0; // 标记是否找到符合条件的路径

// 第一步：计算最短路径长度
void dfs_find_min(int currX, int currY) {
    visited[currX][currY] = 1;
    
    if (currX == endX && currY == endY) {
        if (length < minimum) {
            minimum = length;
        }
        visited[currX][currY] = 0;
        return;
    }

    for (int i = 0; i < 4; i++) {
        int newX = currX + moveX[i];
        int newY = currY + moveY[i];
        if (newX >= 0 && newY >= 0 && newX < x && newY < y && grid[newX][newY] != '#' && !visited[newX][newY]) {
            length++;
            dfs_find_min(newX, newY);
            length--;
        }
    }
    visited[currX][currY] = 0;
}

// 第二步：按优先级寻找并标记最短路径
void dfs_mark_path(int currX, int currY) {
    visited[currX][currY] = 1;
    path[currX][currY] = 1;
    
    if (currX == endX && currY == endY) {
        found = 1;
        return;
    }

    for (int i = 0; i < 4 && !found; i++) {
        int newX = currX + moveX[i];
        int newY = currY + moveY[i];
        if (newX >= 0 && newY >= 0 && newX < x && newY < y && grid[newX][newY] != '#' && !visited[newX][newY] && length + 1 <= minimum) {
            length++;
            dfs_mark_path(newX, newY);
            if (!found) { // 未找到则回溯路径标记
                path[newX][newY] = 0;
                length--;
            }
        }
    }
}

int main() {
    scanf("%d %d", &y, &x);
    for (int i = 0; i < x; i++) {
        scanf("%s", grid[i]);
    }

    // 定位起点和终点
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            if (grid[i][j] == 'S') {
                startX = i;
                startY = j;
            } else if (grid[i][j] == 'E') {
                endX = i;
                endY = j;
            }
        }
    }

    // 第一步：找最短路径长度
    memset(visited, 0, sizeof(visited));
    length = 0;
    dfs_find_min(startX, startY);

    if (minimum == 2147483647) {
        printf("tujuan tidak ditemukan\n");
        return 0;
    }

    // 第二步：按优先级标记最短路径
    memset(visited, 0, sizeof(visited));
    memset(path, 0, sizeof(path));
    length = 0;
    found = 0;
    dfs_mark_path(startX, startY);

    // 生成输出网格
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            if (path[i][j] && grid[i][j] != 'S' && grid[i][j] != 'E') {
                printf("x");
            } else {
                printf("%c", grid[i][j]);
            }
        }
        printf("\n");
    }

    return 0;
}

修复说明 #

• 拆分DFS为两个阶段，先确定最短路径长度，再按优先级寻找路径，避免路径覆盖
• 修正方向向量，严格匹配「右、左、上、下」的优先级
• 使用单独的path数组记录最终路径，避免修改原始网格导致的逻辑混乱
• 加入found标记，找到符合条件的路径后立即终止搜索，确保优先级最高的路径被保留

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