大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

C++实现迷宫的具体代码-创新互联

小编给大家分享一下C++实现迷宫的具体代码,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!

创新互联公司公司2013年成立,是专业互联网技术服务公司,拥有项目成都网站建设、成都网站设计网站策划,项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命,1280元常德做网站,已为上家服务,为常德各地企业和个人服务,联系电话:18982081108

一、 实验目的:

(1) 熟练掌握链栈的基本操作及应用。
(2) 利用链表作为栈的存储结构,设计实现一个求解迷宫的非递归程序。

二、实验内容:

【问题描述】

以一个m×n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对信任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。

【基本要求】

首先实现一个链表作存储结构的栈类型,然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出,其中:(i,j)指示迷宫中的一个坐标,d表示走到下一坐标的方向。如:对于下列数据的迷宫,输出的一条通路为:(1,1,1),(1,2,2),(2,2,2),(3,2,3),(3,1,2),……。

【测试数据】/strong>

迷宫的测试数据如下:左上角(1,1)为入口,右下角(8,9)为出口。
1   2   3   4   5   6   7   8
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0

【实现提示】

计算机解迷宫通常用的是“穷举求解”方法,即从入口出发,顺着某一个方向进行探索,若能走通,则继续往前进;否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通路。假如所有可能的通路都探索到则未能到达出口,则所设定的迷宫没有通睡。
可以二维数组存储迷宫数据,通常设定入口点的下标为(1,1),出口点的下标为(n,n)。为处理方便起见,可以迷宫的四周加一圈障碍。对于迷宫任一位置,均可约定有东、南、西、北四个方向可通。

【选作内容】

(1) 编写递归形式的算法,求得迷宫中所有可能的通路;
(2) 以方阵形式输出迷宫及其通路。

网友提供了一段解决算法:

#include
#include

#define m 4//行

#define n 4//列


struct xy
{
  int x;
  int y;
};
typedef struct stack
{
  struct xy coordinate;
  struct stack* next;
}stack;

void init(stack* p)
{
  
  p->next = NULL;
}

void push(stack* p,struct xy cdnt)
{
  stack* temp = p;
  while(temp->next != NULL)
    temp = temp->next;
  stack* newValue = (stack*)malloc(sizeof(struct stack)*1);
  newValue->coordinate = cdnt;
  newValue->next = temp->next;
  temp->next = newValue;
}

void pop(stack* p)
{
  stack* tempp = p;
  stack* temp = p->next;
  while(temp->next != NULL)
    temp = temp->next,tempp = tempp->next;
  tempp->next = NULL;
  free(temp);
}

void browse(stack* p)
{
  stack* temp = p->next;
  while(temp != NULL)
    printf("(%d,%d)\n",temp->coordinate.y,temp->coordinate.x),temp = temp->next;
}

struct xy getEnd(struct stack* p)
{
  stack* temp = p;
  while(temp->next != NULL)
    temp = temp->next;
  return temp->coordinate;
}

int getSize(stack* p)
{
  int size = 0;
  stack* temp = p->next;
  while(temp != NULL)
  {
    size++;
    temp = temp->next;
  }
  return size;
}
int main()
{

  int path[m+1][n+1] = {0};
  int col = 0,row = 0;
  int i = 0,j = 0;
  int temp_col = 0,temp_row = 0,t_col = 0,t_row = 0;
  int flag = 0;
  struct xy t_pair;
  //stack A,B;

  stack* Ahead = (stack*)malloc(sizeof(struct stack)*1);
  stack* Bhead = (stack*)malloc(sizeof(struct stack)*1);
  init(Ahead); init(Bhead);

  for(;i::iterator iter = B.end() - 1;

          col = getEnd(Bhead).x + 1;row = getEnd(Bhead).y;//回到上一次分叉处,搜索右侧路径

          pop(Ahead);
          pop(Bhead);
          continue;
        }
        else
          return 1;
      }
      //下面是,右边不是

      if(path[row + 1][col] == 1 && path[row][col + 1] == 0)
      {
        t_pair.x = col;t_pair.y = row;
        push(Ahead,t_pair);
        row++;
        continue;
      }
      //下面不是,右边是

      if(path[row + 1][col] == 0 && path[row][col + 1] == 1)
      {
        t_pair.x = col;t_pair.y = row;
        push(Ahead,t_pair);
        col++;
        continue;
      }
      

    }
  }
  if(!flag)
    printf("There is no way\n");
  return 0;
}

以上是“C++实现迷宫的具体代码”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注创新互联网站建设公司行业资讯频道!

另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


文章名称:C++实现迷宫的具体代码-创新互联
标题来源:http://dzwzjz.com/article/heips.html
在线咨询
服务热线
服务热线:028-86922220
TOP