迷宫求解。该怎么解决

迷宫求解。。。
输入地迷宫：
8 10
1 1 1 1 1 1 1 1
1 0 1 1 0 1 0 1
1 0 1 0 0 1 0 1
1 1 0 3 1 0 1 1
1 0 0 1 0 0 4 1
1 0 0 0 0 1 1 1
1 0 1 0 0 1 0 1
1 0 1 0 0 0 1 1
1 1 1 1 0 0 0 1
1 1 1 1 1 1 1 1

C/C++ code

#include "stdio.h"#include "stdlib.h"typedef struct stack{    int serial;//序号，可有可无，为了方便就有吧    char x;    char y;    char dir;//方向，0123代表左上右下    struct stack *prev;//上一个    struct stack *next;//下一个}Sta,*pSta;int num;//当前栈数pSta head, temp ,tail;int main(){    int **mode1,**mode2;    int x,y;    int i,j,z;    int m1,n1;    int m,n;    num=0;    scanf("%d%d",&x,&y);        mode1=(int **)malloc(y*sizeof(int *));        mode2=(int **)malloc(y*sizeof(int *));    for(i=0;i<y;i++)    {        mode1[i]=(int *)malloc(x*sizeof(int));        mode2[i]=(int *)malloc(x*sizeof(int));    }    for(i=0;i<y;i++)        for(j=0;j<x;j++)        {            scanf("%d",&mode1[i][j]);            if(mode1[i][j]==3)            {                m=i;                n=j;            }            mode2[i][j]=0;        }    temp=(pSta)malloc(sizeof(Sta));    temp->next=NULL;    head=tail=temp;    temp=(pSta)malloc(sizeof(Sta));    temp->x=m;    temp->y=n;    temp->dir=4;    temp->serial=++num;    tail->next=temp;    temp->prev=tail;    tail=temp;    temp->next=(pSta)1;    for(z=0;z<4;z++)    {        if( z==0 && ( temp->prev==NULL || temp->prev->dir!=2) )//左边（上一个不能是右边）        {            m = temp->x;n = temp->y+1;//左边一个点的坐标            if(m>=0 && m<=y && n>=0 && n<=x&& mode2[m][n]==0)//必须是有效点，下同            {                if(mode1[m][n]==0)//如果是0，入栈，以下同                {                    temp->dir = z;//记录最后一次探路方向                    temp->next = (pSta)malloc(sizeof(Sta));//栈的新成员                    temp->next->prev = temp;                    temp = temp->next;//temp指向新成员                    temp->x = m;                    temp->y = n;                    temp->dir = 0;//新成员要从0路劲开始探路                    temp->serial = ++num;//新序号                    temp->next = (pSta)1;                    z = -1;//i重置                    mode2[m][n]=1;                }                else if(mode1[m][n]==4)//4结束                    {                        m1=m;                        n1=n;                        temp->next = NULL;                    }            }        }        else if( z==1 && ( temp->prev==NULL || temp->prev->dir!=3) )        {            m = temp->x-1;n = temp->y;            if(m>=0 && m<=y && n>=0 && n<=x&& mode2[m][n]==0)            {                if(mode1[m][n]==0 )                {                    temp->dir = z;                    temp->next = (pSta)malloc(sizeof(Sta));                    temp->next->prev = temp;                    temp = temp->next;                    temp->x = m;                    temp->y = n;                    temp->dir = 0;                    temp->serial = ++num;                    temp->next = (pSta)1;                    z = -1;                    mode2[m][n]=1;                }                else if(mode1[m][n]==4)                    {                        m1=m;                        n1=n;                        temp->next = NULL;                    }            }        }        else if( z==2 && ( temp->prev==NULL || temp->prev->dir!=0) )        {            m = temp->x;n = temp->y-1;            if(m>=0 && m<=y && n>=0 && n<=x&& mode2[m][n]==0)            {                if(mode1[m][n]==0)                {                    temp->dir = z;                    temp->next = (pSta)malloc(sizeof(Sta));                    temp->next->prev = temp;                    temp = temp->next;                    temp->x = m;                    temp->y = n;                    temp->dir = 0;                    temp->serial = ++num;                    temp->next = (pSta)1;                    z = -1;                    mode2[m][n]=1;                }                else if(mode1[m][n]==4)                    {                        m1=m;                        n1=n;                        temp->next = NULL;                    }            }        }        else if( z==3 && ( temp->prev==NULL || temp->prev->dir!=1) )        {            m = temp->x+1;n = temp->y;            if(m>=0 && m<=y && n>=0 && n<=x&& mode2[m][n]==0)            {                if(mode1[m][n]==0)                {                    temp->dir = i;                    temp->next = (pSta)malloc(sizeof(Sta));                    temp->next->prev = temp;                    temp = temp->next;                    temp->x = m;                    temp->y = n;                    temp->dir = 0;                    temp->serial = ++num;                    temp->next = (pSta)1;                    z = -1;                    mode2[m][n]=1;                }                else if(mode1[m][n]==4)                {                        m1=m;                        n1=n;                        temp->next = NULL;                    }            }        }        if(temp->next==NULL)            break;        if(z==3)//到最后路劲依然无解，则出栈        {            if(temp->prev!=NULL)            {                temp = temp->prev;                free(temp->next);                z = temp->dir;            }            else            {                printf("此迷宫无解\n");                return 0;            }        }    }    temp=head->next;    tail=tail->next;    while(temp!=NULL)    {        printf("%d,%d\n",temp->y,temp->x);    }    printf("%d,%d\n",temp->y,temp->x);    printf("%d,%d\n",n1,m1);    return 0;} 
 

总是报错。。。

[解决办法]
 
#include<queue>
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int x1,x2,y1,y2;
int ac[9][9];
int he[]={1,-1,0,0},zo[]={0,0,-1,1};
int ok[9][11]=
{
 1 1 1 1 1 1 1 1
1 0 1 1 0 1 0 1
1 0 1 0 0 1 0 1
1 1 0 3 1 0 1 1
1 0 0 1 0 0 4 1
1 0 0 0 0 1 1 1
1 0 1 0 0 1 0 1
1 0 1 0 0 0 1 1
1 1 1 1 0 0 0 1
1 1 1 1 1 1 1 1
};
struct shu
{
int x,y,step;
};
int BFS()
{
queue<shu>q;//队列容器
int a,b,i;
shu bfs={x1,y1,0};
ac[x1][y1]=1;
q.push(bfs);//入队
while(!q.empty())//队列是否为空
{
bfs=q.front();//出对首
if(bfs.x==x2&&bfs.y==y2)
break;
q.pop();//出对
for(i=0;i<4;i++)
{ a=bfs.x+he[i];
b=bfs.y+zo[i];
if(a>0&&a<=8&&b>0&&b<=9&&ac[a][b]==0&&ok[a][b]==0)
{ shu bb={a,b,bfs.step+1};
q.push(bb);
ac[a][b]=1;
}
}
}
/*while(!q.empty())
q.pop();*/
return bfs.step;
}
int main()
{
int x,cc;
scanf("%d",&x);
while(x--)
{ memset(ac,0,sizeof(ac));
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
cc=BFS();

printf("%d\n",cc);
}
return 0;
}

查看更多 下一篇