在 C 中解决迷宫并打印正确的路径

Question

我正在尝试编写代码来解决迷宫中的老鼠问题。 “1”代表墙壁，“0”代表自由路径。所有采用的路径都存储在二维数组路径[200][2]中。还通过将路径字符替换为“*”来打印路径解决方案。此外，我正在用“1”替换已经采用的路径，这样我们就不会再次遵循该路径。

我的代码：

#include<stdio.h>

int main()
{
char maze[10][10],mazeO[10][10];
int path[200][2],count=-1,N,M,cx,cy,sx,sy,ex,ey;

printf("\nEnter the maze limit(Max=10): (M & N)");
    scanf("%d%d",&M,&N);

    printf("\nEnter the maze:\n");

    for(int i=0;i<M;++i) {
        for(int j=0;j<N;++j)
        {
                scanf(" %c",&maze[i][j]);
                mazeO[i][j]=maze[i][j];
        }
    }
    printf("\nEnter the source cordinates(sx,sy):");
    scanf("%d%d",&sx,&sy);  

    printf("\nEnter the target cordinates(ex,ey):");
    scanf("%d%d",&ex,&ey);

    cx=sx;cy=sy;
    while(cx!=ex || cy!=ey)
    {
        if(maze[cx][cy+1]=='0'&&(cy+1)<N)
        {   
            maze[cx][cy] = '1';
            count++;
            path[count][0]=cx;
            path[count][1]=cy;

            cy=cy+1;
         }
        else if(maze[cx-1][cy]=='0'&&(cx-1)>0)
        {   
            maze[cx][cy] = '1';
            count++;
            path[count][0]=cx;
            path[count][1]=cy;

            cx=cx-1;
         }
        else if(maze[cx][cy-1]=='0'&&(cy-1)>0)
        {   
            maze[cx][cy] = '1';
            count++;
            path[count][0]=cx;
            path[count][1]=cy;

            cy=cy-1;
         }
        else if(maze[cx+1][cy]=='0'&&(cx+1)<M)
        {
            maze[cx][cy] = '1';
            count++;
            path[count][0]=cx;
            path[count][1]=cy;

            cx=cx+1;
         }
         else
         {
            cx=path[count][0];
            cy=path[count][1];
            count--;    
         }
    }

     for(int i=0;i<=count;i++)
        mazeO[path[i][0]][path[i][1]]='*';

     mazeO[ex][ey]='*';

    for(int i=0;i<M;++i)
    {

        for(int j=0;j<N;++j)
        {
            printf(" %c",mazeO[i][j]);
        }
        printf("\n");
    }
}

当我尝试运行上面的代码时输入以下内容：

M = 6    N = 7
sx = 1   sy = 0
ex = 4   ey = 6

给定输入迷宫：

1 1 1 1 1 1 1
0 0 0 0 0 1 1
1 1 0 1 1 1 1 
0 0 0 1 1 1 1 
1 1 0 0 0 0 0 
1 1 1 1 1 1 1

我在 Ubuntu 中遇到分段错误。我无法找到我做错的地方。为什么我会收到此分段错误？

编辑：

我已经根据评论中的建议编辑了代码：

#include<stdio.h>

int main()
{
char maze[10][10],mazeO[10][10];
int path[200][2],count=-1,N,M,cx,cy,sx,sy,ex,ey;

printf("\nEnter the maze limit(Max=10): (M & N)");
    scanf("%d%d",&M,&N);

    printf("\nEnter the maze:\n");

    for(int i=0;i<M;++i) {
        for(int j=0;j<N;++j)
        {
                scanf(" %c",&maze[i][j]);
                mazeO[i][j]=maze[i][j];
        }
    }
    printf("\nEnter the source cordinates(sx,sy):");
    scanf("%d%d",&sx,&sy);  

    printf("\nEnter the target cordinates(ex,ey):");
    scanf("%d%d",&ex,&ey);

    cx=sx;cy=sy;
    while(cx!=ex || cy!=ey)
    {
        if((cy+1)<N && maze[cx][cy+1]=='0')
        {   
            maze[cx][cy] = '1';
            count++;
            path[count][0]=cx;
            path[count][1]=cy;

            cy=cy+1; 
        }
        else if((cx-1)>0 && maze[cx-1][cy]=='0')
        {   
            maze[cx][cy] = '1';
            count++;
            path[count][0]=cx;
            path[count][1]=cy;

            cx=cx-1;
         }
        else if((cy-1)>0 && maze[cx][cy-1]=='0')
        {   
            maze[cx][cy] = '1';
            count++;
            path[count][0]=cx;
            path[count][1]=cy;

            cy=cy-1;
         }
        else if((cx+1)<M && maze[cx+1][cy]=='0')
        {
            maze[cx][cy] = '1';
            count++;
            path[count][0]=cx;
            path[count][1]=cy;

            cx=cx+1;
         }
         else
         {
            cx=path[count][0];
            cy=path[count][1];

            count--;    
         }
    }

     for(int i=0;i<=count;i++)
        mazeO[path[i][0]][path[i][1]]='*';

     mazeO[ex][ey]='*';

    for(int i=0;i<M;++i)
    {

        for(int j=0;j<N;++j)
        {
            printf(" %c",mazeO[i][j]);
        }
        printf("\n");
    }
}

仍然发生分段错误。我在 Windows OS 和 windows 上试过它没有给出任何错误，但它没有打印正确的路径迷宫。

最终工作解决方案：

我只需要 maze[cx][cy] = '1' 在 else 循环中。还将 if 循环条件 (cy-1)>0 更改为 (cy-1)>=0 并将 (cx-1)>0 更改为 (cx-1)>=0。还在 if(count>=0) 循环中包含 count--。

Answer 1

正如@Klas-Lindbäck 已经提到的，您不处理计数变为负数。然后它将开始索引数组外的 path[] 并且坏事发生了。

找不到路径是因为(5,6)是一堵墙。也许你的意思是 (4,6) ?

此外，左列和上行不允许访问，因为您检查的是 (cy-1)>0 而不是 >= 0。

除此之外，您的回溯步骤需要将 maze[cx][cy] 设置为 1，以防止一遍又一遍地进入相同的路径。

Answer 2

很多问题：

while 检查 maze[cx][cy] while 内的所有 if 迷宫数据存储到 mazeO 矩阵中。或者双 for 循环应该填充 maze 而不是 mazeO.
您的出口坐标指向一堵墙，因此无法退出。
您的代码无法"choose"移动方向。因此，从您的参数开始，"player" 在位置 3 和 4 之间的行 1 上连续乒乓（左右移动）。
在第 3 点中描述的 200 次乒乓之后 count 将解决您的路径矩阵越界问题，因此 Undefined Behavior 在您的情况下是 分段错误

在 C 中解决迷宫并打印正确的路径

Solving Maze And Printing The Correct Path in C

c

arrays

stack

maze

data-structures