在C中使用DFS求解迷宫最短路径的问题

Question

我正在使用 C 语言开发一个使用深度优先搜索 (DFS) 算法的迷宫求解程序。该程序旨在查找从开始 ('S') 到结束 ('E') 的最短路径由二维网格表示的迷宫。目标是优先向右走，然后向左走，然后向上走，最后向下走。然而，我遇到了一个问题，即使在改变方向向量之后，算法似乎也会优先考虑向下。

#include <stdio.h>
char grid[15][15];
int visited[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;
void depthfirstsearch(int currX, int currY) {
    visited[currX][currY] = 1;
 
    if (currX == endX && currY == endY) {
        if (length < minimum) {
            minimum = length;
            for (int i = 0; i < x; i++) {
                for (int j = 0; j < y; j++) {
                    if (visited[i][j] && grid[i][j] != 'S' && grid[i][j] != 'E') {
                        grid[i][j] = 'x';
                    } else if (grid[i][j] == 'x') {
                        grid[i][j] = '.'; 
                    }
                }
            }
        }
        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++;
            depthfirstsearch(newX, newY);  
            length--; 
        }
    }

    visited[currX][currY] = 0; 
}
int main() {
    scanf("%d %d", &x, &y);
    for(int i = 0; i < y; 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;
            }
        }
    }
    length = 0;
    depthfirstsearch(startX, startY);
    if(minimum == 2147483647){
        printf("destination not found\n");
    } 
    else{
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                printf("%c", grid[i][j]);
            }
            printf("\n");
        }
    }
    return 0;
}

我已经尝试修改 moveX 和 moveY 数组以优先考虑右左上下，但程序仍然优先考虑向下 我用这个。

int moveX[4] = {1, -1, 0, 0};
int moveY[4] = {0, 0, 1, -1};

我尝试更改为

int moveX[4] = {0, 0, -1, 1};
int moveY[4] = {1, -1, 0, 0};

它可以工作，但如果网格是

6 7
######
#E####
#.####
#.####
#.####
#.####
#S####

找不到目的地

还有

6 5
######
#...E#
#....#
#S...#
######
######
#xxxE#
#x...#
#S...#
######

它优先考虑向上而不是向右

此外，当我切换循环的顺序时（for (int i = 0; i < x; i++) and for (int j = 0; j < y; j++)), I encountered issues when the grid size is not symmetrical.

任何有关算法为何未正确优先考虑方向的见解以及有关如何解决此问题的建议将受到高度赞赏。有没有更好的方法来构造我的 DFS 算法来解决迷宫，或者在处理非对称网格时我应该注意哪些具体注意事项？

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

所以我放弃了这个想法，并尝试改变方向向量，但它仍然优先考虑

正确的应该是

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

我暂时不知道任何其他方法 我还是不明白为什么我

Answer 1

将 main 的开头更改为

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

如果您打印了“未找到”案例的网格，您可能会注意到板的一部分丢失了。

对 2D 数组进行寻址的习惯方式是

array[y][x]

。您的输入与此一致，但您的使用情况不一致。

结论：你似乎颠倒了某些地方的尺寸。