2 isaver23 isaver23 于 2014.12.05 17:29 提问

关于队列迷宫的一个问题

一个关于队列求解迷宫的小问题,发现把主函数里设置的出口坐标改动的时候会出现运行错误,比如说改成(1,1,8,1)就会有错。。。实在是有点看不懂了,发帖求教前辈们出手帮忙看看问题出在哪,要怎么改啊???编译软件codeblocks

/*

  • 迷宫求解 * */ #include #include #define MAXSIZE 1000 #define M 10 int mg[M][M] = { // 此迷宫有三条路径 {1,1,1,1,1,1,1,1,1,1}, {1,0,0,0,1,1,1,1,1,1}, {1,0,1,0,0,0,0,1,1,1}, {1,0,0,1,1,1,0,1,1,1}, {1,1,0,1,1,1,0,0,0,1}, {1,1,0,1,1,1,1,1,0,1}, {1,0,0,0,0,0,1,1,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1} };

// ------------------ 栈定义 -------------------------
struct{
int i,j; // 方块的位置
int pre; // 本路径中上一方块在路径中的下标
}Qu[MAXSIZE];

void print(int front);
/*

  • 利用队列求解迷宫
    */
    void mgpath(int x1, int y1, int x2, int y2)
    {
    int front,rear;
    int find =0;
    int i,j;
    int di;
    front=-1;
    rear=-1;

    rear++; // (x1,y1)入队
    Qu[rear].i = x1;
    Qu[rear].j = y1;
    Qu[rear].pre = -1;

    mg[x1][y1]=-1; // 置为-1, 以免重复搜索
    while(front<=rear && !find)
    {
    front++; // 出队
    i = Qu[front].i;
    j = Qu[front].j;
    if(i == x2 && j == y2) // 出口
    {
    find = 1;
    print(front);
    return;
    }

    for(di=0;di<3;di++)
    {
        switch(di)
        {
            case 0:
                i=Qu[front].i - 1;
                j=Qu[front].j;
            break;
            case 1:
                i=Qu[front].i;
                j=Qu[front].j+1;
            break;
            case 2:
                i=Qu[front].i + 1;
                j=Qu[front].j;
            break;
            case 3:
                i=Qu[front].i;
                j=Qu[front].j - 1;
            break;
        }
        if(mg[i][j] == 0) // 找到
        {
            rear++; // 插入
            Qu[rear].i = i;
            Qu[rear].j = j;
            Qu[rear].pre = front;
            mg[i][j] = -1;
        } // if
    } // for
    

    } // while
    if(!find)
    printf("找不到可走路径");
    }

void print(int front)
{
int f,t;
int ns=0;
f=front;
printf("\n");
do{
t = f;

    f = Qu[f].pre;
    Qu[t].pre = -1; //把当前的设为 -1
}while(f!=0);
printf("路径如下:\n");
f=0;
while(f<MAXSIZE)
{
    if(Qu[f].pre==-1)
    {
        ns++;
        printf("(%d,%d)  ",Qu[f].i,Qu[f].j);
        if(ns%5 == 0)
            printf("\n");
    }
    f++;
}

}
void main()
{
int i,j;
printf("迷宫设置如下:\n\n");
for(i = 0; i < M; i++)
{
for(j = 0; j < M; j++)
{
printf("%d ",mg[i][j]);
}
printf("\n");
}
mgpath(1,1,8,8);
}

1个回答

eagleyan
eagleyan   Rxr 2014.12.06 01:05

我没有仔细看代码,但是循环部分没有检查边界(最上,最下,最左,最右)。明显是个bug

Csdn user default icon
上传中...
上传图片
插入图片