作业题求解，卡住了.总是报错，求解，多谢高手了.

作业题求解，卡住了......总是报错，求解，谢谢高手了...
标题：迷宫问题
时限： 100000 ms
内存限制： 100000 K
总时限： 3000 ms
描述：迷宫问题

迷宫是一个二维矩阵,其中1为墙,0为路,3为入口,4为出口.要求从入口开始,从出口结束,按照下,左,上,右的顺序来搜索路径.
输入：迷宫宽度w 迷宫高度h
迷宫第一行
迷宫第二行
...
迷宫第h 行
输出：入口横坐标1 入口纵坐标1
横坐标2 纵坐标2
横坐标3 纵坐标3
横坐标4 纵坐标4
...
横坐标n-1 纵坐标n-1
出口横坐标n 出口纵坐标n
输入样例： 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
输出样例： 3 3
2 3
2 4
2 5
3 5
3 6
3 7
4 7
4 6
4 5
4 4
5 4
6 4

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()
{
    char **mode1,**mode2;
    int x,y;
    int i,j,z;
    int m1,n1;
    int m,n;
    num=0;
    scanf("%d%d",&x,&y);
        mode1=(char **)malloc(y*sizeof(char *));
        mode2=(char **)malloc(y*sizeof(char *));
    for(i=0;i<y;i++)
    {
        mode1[i]=(char *)malloc(x*sizeof(char));
        mode2[i]=(char *)malloc(x*sizeof(char));
    }
    for(i=0;i<y;i++)
        for(j=0;j<x;j++)
        {
            scanf("%d",&mode1[i][j]);
            mode2[i][j]=0;
        }
    head=(pSta)malloc(sizeof(Sta));
    head->next=NULL;
    temp=tail=head;
    for(i=0;i<y;i++)
        for(j=0;j<x;j++)
        {
            if(mode1[i][j]==3)
            {
                temp->x=i;
                temp->y=j;
                temp->serial=num;
                num++;
                head=tail=temp;
                temp->next=(pSta)1;
                mode2[i][j]=1;
                goto lv1;
            }
        }
    lv1:for(z=0;z<4;z++)
    {
        if( z==0 && ( temp->prev==NULL || temp->prev->dir!=2) )//左边（上一个不能是右边）
        {
            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)//如果是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;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==2 && ( temp->prev==NULL || temp->prev->dir!=0) )
        {
            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==3 && ( temp->prev==NULL || temp->prev->dir!=1) )
        {
            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 = 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;
            }
        }
    }
    for(temp = head;temp->next!=NULL;temp = temp->next)
        printf("%d,%d\n",temp->y,temp->x);
    printf("%d,%d\n",temp->y,temp->x);
    printf("%d,%d\n",n1,m1);
    return 0;
}

作业题求解，卡住了.总是报错，求解，多谢高手了.

相关推荐