ITKeyword,专注技术干货聚合推荐

注册 | 登录

数据结构:栈应用_求解迷宫问题2

chemingliang 分享于

2020腾讯云双十一活动,全年最低!!!(领取3500元代金券),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1073

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
地址https://www.aliyun.com/minisite/goods

推荐:数据结构之栈的应用----迷宫求解

/***********程序设计思想*************/ (1)迷宫地图相关: 利用动态二维数组来初步勾勒出迷宫: 建议先用malloc申请一维数组,再用calloc申请每个元素中的一

/************************************************************************/

/* 数据结构:栈应用:求解迷宫问题                                                                   */

/* 挑灯看剑-shuchangs@126.com 2010-10                                                             */

/* 云歌国际(Cloud Singers International) www.cocoral.com                          */

/************************************************************************/

//上接版面 《数据结构:栈应用_求解迷宫问题1》

 

 

/************************************************************************/

/* 以下为迷宫求解问题                                                                                 */

/************************************************************************/

 

void mazeExperiment()

{

       void printMatrix(int (*mtx)[9], int m, int n);

       void printMzePath(Stack S, int (*mtx)[9], int m, int n);

       static Status visa(CurPos* foot, char direction);

       static void step(CurPos* END, CurPos* foot, Stack* stack, Node* node);

 

       //定义迷宫矩阵,1表示通行,0表示禁止

       //约定迷宫矩阵四壁均为禁止

       int mtx[9][9] =

       {

              {0,0,0,0,0,0,0,0,0},

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

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

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

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

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

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

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

              {0,0,0,0,0,0,0,0,0}

       };

 

       Stack stack =

       {

              0, NULL, NULL

       };  //定义一个空栈

 

       Node node =

       {

              NULL, NULL, NULL

       };  //用来返回出栈元素

 

       CurPos* foot, * start, * end;//定义足迹指针,开始指针和结束指针

 

       CurPos footprint[9][9];//定义一个足迹矩阵

       int m = 9;//足迹矩阵行数

       int n = 9;//足迹矩阵列数

       COUNT i, j;//足迹坐标

 

       //初始化足迹矩阵

       for (i = 0; i <= m - 1; i++)

       {

              for (j = 0; j <= n - 1; j++)

              {

                     footprint[i][j].data = mtx[i][j];

                     footprint[i][j].visited = FALSE;

                     footprint[i][j].x = i;

                     footprint[i][j].y = j;

                     if (i == 0 && j == 0) //左上顶点

                     {

                            footprint[i][j].up = NULL;

                            footprint[i][j].down = &footprint[i + 1][j];

                            footprint[i][j].left = NULL;

                            footprint[i][j].right = &footprint[i][j + 1];

                     }

                     else if (i == 0 && j == n - 1) //右上顶点

                     {

                            footprint[i][j].up = NULL;

                            footprint[i][j].down = &footprint[i + 1][j];

                            footprint[i][j].left = &footprint[i][j - 1];

                            footprint[i][j].right = NULL;

                     }

                     else if (i == m - 1 && j == 0) //左下顶点

                     {

                            footprint[i][j].up = &footprint[i - 1][j];

                            footprint[i][j].down = NULL;

                            footprint[i][j].left = NULL;

                            footprint[i][j].right = &footprint[i][j + 1];

                     }

                     else if (i == m - 1 && j == n - 1) //右下顶点

                     {

                            footprint[i][j].up = &footprint[i - 1][j];

                            footprint[i][j].down = NULL;

                            footprint[i][j].left = &footprint[i][j - 1];

                            footprint[i][j].right = NULL;

                     }

                     else if (i == 0 && j != 0 && j != n - 1) //上边框

                     {

                            footprint[i][j].up = NULL;

                            footprint[i][j].down = &footprint[i + 1][j];

                            footprint[i][j].left = &footprint[i][j - 1];

                            footprint[i][j].right = &footprint[i][j + 1];

                     }

                     else if (i == m - 1 && j != 0 && j != n - 1) //下边框

                     {

                            footprint[i][j].up = &footprint[i - 1][j];

                            footprint[i][j].down = NULL;

                            footprint[i][j].left = &footprint[i][j - 1];

                            footprint[i][j].right = &footprint[i][j + 1];

                     }

                     else if (j == 0 && i != 0 && i != m - 1) //左边框

                     {

                            footprint[i][j].up = &footprint[i - 1][j];

                            footprint[i][j].down = &footprint[i + 1][j];

                            footprint[i][j].left = NULL;

                            footprint[i][j].right = &footprint[i][j + 1];

                     }

                     else if (j == n - 1 && i != 0 && i != m - 1) //右边框

                     {

                            footprint[i][j].up = &footprint[i - 1][j];

                            footprint[i][j].down = &footprint[i + 1][j];

                            footprint[i][j].left = &footprint[i][j - 1];

                            footprint[i][j].right = NULL;

推荐:数据结构(迷宫求解c++)

#include "sqstack.h"Status InitStack(Stack &S){ S.top = 0 ; for( int i = 0 ; i < MaxSize ; i++ ) { S.data[i].di = 0 ; S.data[i]

                     }

                     else //中间元素

                     {

                            footprint[i][j].up = &footprint[i - 1][j];

                            footprint[i][j].down = &footprint[i + 1][j];

                            footprint[i][j].left = &footprint[i][j - 1];

                            footprint[i][j].right = &footprint[i][j + 1];

                     }

              }

       }

 

       start = &footprint[1][1]; //定义起始指针和结束指针,并初始化

       end = &footprint[7][7];

       foot = start;                  //令足迹指针初始指向起始指针

       foot->visited = 1;                //令访问标记为已访问

       StackIn(&stack, *foot);       //当前足迹入栈

       printMzePath(stack, mtx, 9, 9);

       //迷宫遍历规则:每个格子紧挨四个格子,定义为上-下,左-右,按照从右开始、顺时针方向遍历格子

       step(end, foot, &stack, &node); //调用回调函数

       StackPrint(stack, 'B'); //打印栈(迷宫路径)

       printMzePath(stack, mtx, 9, 9);

}

static void step(CurPos* END, CurPos* foot, Stack* stack, Node* rtnNode)

{

       if (foot == END)

       {

              puts("迷宫求解结束!");

       }

       else if (stack->len == 0)

       {

              puts("迷宫求解失败!");

       }

       else if (visa(foot, 'R')) //如果右侧可行,先遍历右方向

       {

              foot->visited = 1; //当前足迹已访问

              StackIn(stack, *foot); //当前足迹入栈

              //StackPrint(*stack, 'B');

              foot = foot->right; //向右前进一步

              step(END, foot, stack, rtnNode);

       }

       else if (visa(foot, 'D'))

       {

              foot->visited = 1;

              StackIn(stack, *foot);

              //StackPrint(*stack, 'B');

              foot = foot->down;

              step(END, foot, stack, rtnNode);

       }

       else if (visa(foot, 'L'))

       {

              foot->visited = 1;

              StackIn(stack, *foot);

              //StackPrint(*stack, 'B');

              foot = foot->left;

              step(END, foot, stack, rtnNode);

       }

       else if (visa(foot, 'U'))

       {

              foot->visited = 1;

              StackIn(stack, *foot);

              //StackPrint(*stack, 'B');

              foot = foot->up;

              step(END, foot, stack, rtnNode);

       }

       else

       {

              foot->visited = 1;

              StackOut(stack, rtnNode); //出栈一位,删除栈顶

              foot = &(rtnNode->data); //foot指针退回到删除结点位置

              //printf("删除结点 foot[%d][%d] = %d\n", foot->x, foot->y,foot->data);

              //StackPrint(*stack, 'B');

              step(END, foot, stack, rtnNode);

       }

}

 

static Status visa(CurPos* foot, char direction)

{

       Status status = FALSE;

       switch (direction)

       {

       case 'L':

              //如果左结点的值可通行,且未被访问

              if (foot->left->data == 1 && foot->left->visited == 0)

                     status = TRUE;

              break;

       case 'R':

              if (foot->right->data == 1 && foot->right->visited == 0)

                     status = TRUE;

              break;

       case 'U':

              if (foot->up->data == 1 && foot->up->visited == 0)

                     status = TRUE;

              break;

       case 'D':

              if (foot->down->data == 1 && foot->down->visited == 0)

                     status = TRUE;

              break;

       default:

              break;

       }

       return status;

}

 

 

void printMatrix(int (*mtx)[9], int m, int n)

{

       COUNT i, j;

       printf("矩阵信息:%d行,%d列!\n", m, n);

       for (i = 0; i < m; i++)

       {

              printf("row=%d   ", i);

              for (j = 0; j < n; j++)

              {

                     printf(" %d ", *(*(mtx + i) + j));

              }

              printf("\n");

       }

}

 

//下接版面 《数据结构:栈应用:求解迷宫问题3》

推荐:数据结构:栈应用_求解迷宫问题3

/************************************************************************/ /* 数据结构:栈应用:求解迷宫问题                                          

/************************************************************************/ /* 数据结构:栈应用:求解迷宫问题                                                                   */ /*

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。