#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define MATRIX_LEN 13

void PrintMaze(int (*PtrMaze)[MATRIX_LEN]);

void RecoveryLocation(int &n,int &m,int &Naddr,int &Maddr);
void RightLocation(int &n,int &m);
void DownLocation(int &n,int &m);
void LeftLocation(int &n,int &m);
void UpLocation(int &n,int &m);

typedef struct{
    int *ntop;
    int *nbase;
    int nstacksize;
}nstack;

void InitNStack(nstack &s);
void PushNStack(nstack &s,int value);
void PopNStack(nstack &s);
int GetNTop(nstack &s);

typedef struct{
    int *mtop;
    int *mbase;
    int mstacksize;
}mstack;

void InitMStack(mstack &s);
void PushMStack(mstack &s,int value);
void PopMStack(mstack &s);
int GetMTop(mstack &s);

void main()
{
    printf("******求解迷宫出路******\n\n");
    int maze[MATRIX_LEN][MATRIX_LEN]={  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                        {0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1},
                        {0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0},
                        {0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0},
                        {0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0},
                        {0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0},
                        {0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0},
                        {0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0},
                        {0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0},
                        {0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0},
                        {0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0},
                        {0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0},
                        {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
    PrintMaze(maze);
    int Naddr=0,Maddr=0;
    int n=0,m=0;
    int Nend=0,Mend=0;
    printf("\n\n输入起点坐标,格式为:*#*  ");
    scanf("%d#%d",&n,&m);
    printf("\n\n输入终点坐标,格式为:*#*  ");
    scanf("%d#%d",&Nend,&Mend);
    int FlagFinish=0;
    nstack NS;
    mstack MS;
    InitNStack(NS);
    InitMStack(MS);
    for(;FlagFinish==0;)
    {
        Naddr=n;
        Maddr=m;
        if(n==Nend&&m==Mend)
        {
            FlagFinish=1;
        }
        RightLocation(n,m);
        if(maze[n][m]==1)
        {
            PushNStack(NS,n);
            PushMStack(MS,m);
            maze[n][m]++;
            continue;
        }
        else if(maze[n][m]!=1)
        {
            RecoveryLocation(n,m,Naddr,Maddr);
            DownLocation(n,m);
            if(maze[n][m]==1)
            {
                PushNStack(NS,n);
                 PushMStack(MS,m);
                maze[n][m]++;
                continue;
            }
            else if(maze[n][m]!=1)
            {
                RecoveryLocation(n,m,Naddr,Maddr);
                LeftLocation(n,m);
                if(maze[n][m]==1)
                {
                    PushNStack(NS,n);
                     PushMStack(MS,m);
                    maze[n][m]++;
                    continue;
                }
                else if(maze[n][m]!=1)
                {
                    RecoveryLocation(n,m,Naddr,Maddr);
                    UpLocation(n,m);
                    if(maze[n][m]==1)
                    {
                        PushNStack(NS,n);
                        PushMStack(MS,m);
                        maze[n][m]++;
                        continue;
                    }
                    else if(maze[n][m]!=1)
                    {
                        RecoveryLocation(n,m,Naddr,Maddr);
                        maze[n][m]=0;
                        PopNStack(NS);
                        PopMStack(MS);
                        n=GetNTop(NS);
                        m=GetMTop(MS);
                        continue;
                    }
                }
            }
        }
    
    }
    while(NS.ntop!=NS.nbase && MS.mtop!=MS.mbase)
    {
        printf("n=%d ",*(--NS.ntop));  
        printf("m=%d\n",*(--MS.mtop));
    }
    //PrintMaze(maze);
}

void InitNStack(nstack &s)
{
    s.nbase=(int *)malloc(100*sizeof(int));
    s.ntop=s.nbase;
    s.nstacksize=100;
}

void PushNStack(nstack &s,int value)
{
    *s.ntop++=value;
}

void PopNStack(nstack &s)
{
    int temp;
    temp=*(--s.ntop);
}

int GetNTop(nstack &s)
{
    int temp;
    temp=*(s.ntop-1);
    return temp;
}

void InitMStack(mstack &s)
{
    s.mbase=(int *)malloc(100*sizeof(int));
    s.mtop=s.mbase;
    s.mstacksize=100;
}

void PushMStack(mstack &s,int value)
{
    *s.mtop++=value;
}

void PopMStack(mstack &s)
{
    int temp;
    temp=*(--s.mtop);
}

int GetMTop(mstack &s)
{
    int temp;
    temp=*(s.mtop-1);
    return temp;
}

void PrintMaze(int (*PtrMaze)[MATRIX_LEN])
{
    int i,j;
    for(i=0;i<MATRIX_LEN;i++)
    {
        for(j=0;j<MATRIX_LEN;j++)
        {
            printf("%d ",*(PtrMaze[i]+j));
        }
        printf("\n");
    }
}

void RecoveryLocation(int &n,int &m,int &Naddr,int &Maddr)
{
    n=Naddr;
    m=Maddr;
}

void RightLocation(int &n,int &m)
{
    n=n;
    m=m+1;
}
void DownLocation(int &n,int &m)
{
    n=n+1;
    m=m;
}
void LeftLocation(int &n,int &m)
{
    n=n;
    m=m-1;
}
void UpLocation(int &n,int &m)
{
    n=n-1;
    m=m;
}