Data-structure-and-algorithm/Maze.cpp at master · dyq-w/Data-structure-and-algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<iostream>

using namespace std;

int mg[10][10] =
{

    {1,1,1,1,1,1,1,1,1,1},
    {1,0,0,1,0,0,0,1,0,1},
    {1,0,0,1,0,0,0,1,0,1},
    {1,0,0,0,0,1,1,0,0,1},
    {1,0,1,1,1,0,0,0,0,1},
    {1,0,0,0,1,0,0,0,0,1},
    {1,0,1,0,0,0,1,0,0,1},
    {1,0,1,1,1,0,1,1,0,1},
    {1,1,0,0,0,0,0,0,0,1},
    {1,1,1,1,1,1,1,1,1,1}
};


typedef struct
{
    int i;    //当前方块的行号
    int j;    //当前方块的列号
    int di;   //di是下一个可走相邻方位的方位号
}Box;

typedef struct
{
    Box data[99];
    int top;
}StType;

bool mgpath(int xi,int yi,int xe,int ye)    //(xi,yi)为入口，（xe,ye）为出口
{
    int i,j,k,di,find;
    StType st;st.top = -1;
    st.top++;
    st.data[st.top].i = xi;st.data[st.top].j = yi;
    st.data[st.top].di = -1;
    mg[xi][yi] = -1;


     while(st.top>-1)
    {
        i=st.data[st.top].i;j=st.data[st.top].j;
        di=st.data[st.top].di;
        if(i==xe&&j==ye)
        {
            printf("迷宫路径如下：\n");
            for(k=0;k<=st.top;k++)
            {
                printf("\t(%d,%d)",st.data[k].i,st.data[k].j);
                if((k+1)%5 == 0)
                    printf("\n");
            }
            printf("\n");
            return true;
        }

    find = 0;
    while(di<4&&find==0)
    {
        di++;
        switch(di)
        {
            case 0:i=st.data[st.top].i-1;j=st.data[st.top].j;
            break;
            case 1:i=st.data[st.top].i;j=st.data[st.top].j+1;
            break;
            case 2:i=st.data[st.top].i+1;j=st.data[st.top].j;
            break;
            case 3:i=st.data[st.top].i;j=st.data[st.top].j-1;
            break;
        }
        if(mg[i][j]==0) find=1;
    }
    if(find ==1)
    {
        st.data[st.top].di = di;
        st.top++;
        st.data[st.top].i=i;st.data[st.top].j=j;
        st.data[st.top].di=-1;
        mg[i][j]=-1;
    }else
    {
        mg[st.data[st.top].i][st.data[st.top].j] = 0;
        st.top--;
    }

  }
  return false;
}


int main()
{
    if(!mgpath(1,1,8,8))
        printf("该迷宫问题没有解！");
        return 0;
}