四向迷宫求解 | LSABLOG

首页 » Program » C/C++ » 正文

四向迷宫求解

利用栈实现迷宫求解通路。
关键点:1.明确四个方向的顺序(顺时针或逆时针)
2.做标记避免重复走到已走的方块
3.找到可走的方块要进栈保存信息
4.若当前方块没路走了,要出栈并且此位置归0(还原为可走方块)

#include <stdio.h>

int map[10][10] =
{
    {1,1,1,1,1,1,1,1},
    {1,0,0,1,0,0,0,1},
    {1,1,0,0,0,1,1,1},
    {1,0,0,1,0,0,0,1},
    {1,0,0,0,0,0,0,1},
    {1,1,1,1,1,1,1,1}
};

int killmaze(int si,int sj,int ei,int ej)
{
    struct
    {
        int i;                  //当前方块行号
        int j;                  //当前方块列号
        int di;                 //下一个相邻可走方位号
    } st[100];
    int top = -1;       //初始化栈顶指针
    int i,j,k,di,f;
    top++;              //初始方块进栈
    st[top].i = si;
    st[top].j = sj;
    st[top].di = -1;
    map[si][sj] = -1;
    while (top>-1)              //栈不空则循环
        {
            i = st[top].i;
            j = st[top].j;
            di = st[top].di;         //取栈顶方块
            if (i==ei&&j==ej)        //找到出口!
                {
                    printf("maze road is:\n");
                    for (k=0; k<=top; k++)
                        {
                            printf("\t(%d,%d)  ",st[k].i,st[k].j);
                        }
                    printf("\n");
                    return 1;
                }
            else                   //没找到出口
                {
                    f = 0;
                    while (di<4&&f==0)       //找下一个可走方块
                        {
                            di++;
                            switch (di)            //四个方向搜索
                                {
                                case 0:
                                    i = st[top].i-1;
                                    j = st[top].j;
                                    break;
                                case 1:
                                    i = st[top].i;
                                    j = st[top].j+1;
                                    break;
                                case 2:
                                    i = st[top].i+1;
                                    j = st[top].j;
                                    break;
                                case 3:
                                    i = st[top].i;
                                    j = st[top].j-1;
                                    break;
                                }
                            if (map[i][j]==0) f = 1;   //找到可走的(map是0)
                        }
                    if (f==1)     //修改原栈顶元素di
                        {
                            st[top].di = di;
                            top++;    //下一个可走方块进栈(刚刚找到的可走的)
                            st[top].i = i;
                            st[top].j = j;
                            st[top].di = -1;
                            map[i][j] = -1;          //避免重复走此方块
                        }
                    else            //没找到可走的方块
                        {
                            map[st[top].i][st[top].j] = 0;    //该方块变为其他路径可走(虽然这个方块往前走不了,但是这个方块可以走啊)
                            top--;                    //该方块退栈(走到你这都没路了肯定退你啦)
                        }
                }
        }
    return 0;
}

int main()
{
    killmaze(1,1,4,6);
    return 0;
}

赞 (0)

Comment