C++實現迷宮的具體代碼

小編給大家分享一下C++實現迷宮的具體代碼，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

一、 實驗目的：

（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）。為處理方便起見，可以迷宮的四周加一圈障礙。對于迷宮任一位置，均可約定有東、南、西、北四個方向可通。

【選作內容】

（１） 編寫遞歸形式的算法，求得迷宮中所有可能的通路；
（２） 以方陣形式輸出迷宮及其通路。

網友提供了一段解決算法：

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

#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<m;i++)
    for(j=0;j<n;j++)
      {
        printf("input 0 or 1\n");
        scanf("%d",&path[i][j]);
      }
  i = j = 0;

  if(path[0][0] == 0 || path[m-1][n-1] == 0)
  {
    printf("There is no way\n");
    return 1;
  }
  while(1)
  {
    //檢驗是否已經到達末尾

    if(col == n-1 && row == m-1 && path[row][col] == 1)
    {
      //到達尾端，意味著找到一條路

      flag = 1;
      printf("Find a way,it's\n");
      browse(Ahead);
      printf("(%d,%d)\n",m-1,n-1);
      if(getSize(Bhead) != 0)
      {
        
        temp_col = getEnd(Bhead).x;
        temp_row = getEnd(Bhead).y;

        while(1)
          if(getEnd(Ahead).x == temp_col && getEnd(Ahead).y == temp_row)
            break;
          else
            pop(Ahead);
        col = temp_col + 1;
        row = temp_row;
        pop(Bhead);

      }
      else
        return 1;
     }

    else//還沒有到末尾的情況

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

      if(path[row + 1][col] == 0 && path[row][col + 1] == 0)
      {
        if(getSize(Bhead))
        {
          //vector<struct xy>::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++實現迷宮的具體代碼”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！