初級版迷宮問題（棧的應用）

 
/*
 （一）初級迷宮問題：
  0：代表通
  1：代表不通
  求迷宮的通路
 （二）步驟：
  1.創建迷宮
     * 從文件中讀取迷宮
     * 開辟二維數組存放迷宮
  2.尋找通路
     * 檢查某位置是否為通
     * 出口位置判斷
     * 走過的路用2標記
     * 利用棧回溯
 （三）問題
  1.解決回溯中重復探測：遞歸
  2.最優解：迷宮的最短通路
*/

#include <iostream>
#include <stdlib.h>
#include <assert.h>
#include <stack>
#define _CRT_SECURE_NO_WARNINGS 1
#define N 10
using namespace std;
struct Pos
{
 size_t _row;  //行
 size_t _col;  //列
};
void GetMap(int* m, int n)
{
 int i = 0;
 int j = 0;
 assert(m);
 FILE* fin = fopen("C:\\學習\\code\\數據結構\\MazeMap\\MazeMap.txt","r");
 assert(fin);
 for(i = 0; i < n; i++)
 {
  for(j = 0; j < n;)
  {
   char ch = fgetc(fin);
   if(ch == '0'||ch == '1')
   {
    m[i*n+j] = ch - '0';
    j++;
   }
  }
 }
}
void PrintMap(int* m, int n)
{
 assert(m);
 int i = 0;
 int j = 0;
 for(i = 0; i < n; i++)
 {
  for(j = 0; j < n; j++)
  {
   cout<<m[i*n+j]<<' ';
  }
  cout<<endl;
 }
}
bool CheckIsAccess(int* m, int n, const Pos& next)
{
 if(next._row >= 0 && next._row < n 
  && next._col >= 0 && next._col < n
  && m[next._row*n+next._col] == 0)
 {
  return true;
 }
 else
 {
  return false;
 }
}
bool SearchMazePath(int* m, int n, Pos enrty,stack<Pos> paths)
{
 assert(m);
 paths.push(enrty);
 while(!paths.empty())
 {
  Pos cur = paths.top();
  m[cur._row * n + cur._col] = 2;
  //檢查是否找到出口
  if(cur._row == n-1)
  {
   return true;
  }
  Pos next = cur;
  //上
  next._row--;
  if(CheckIsAccess(m, n, next))
  {
   paths.push(next);
   continue;
  }
  next = cur;
  //右
  next._col++;
  if(CheckIsAccess(m, n, next))
  {
   paths.push(next);
   continue;
  }
  next = cur;   //next歸位
  //下
  next._row++;
  if(CheckIsAccess(m, n, next))
  {
   paths.push(next);
   continue;
  }
  next = cur;
  //左
  next._col--;
  if(CheckIsAccess(m, n, next))
  {
   paths.push(next);
   continue;
  }
 
  paths.pop();
 }
 return false;
}
int main()
{
 int map[N][N]= {0};
 GetMap((int*)map, N);
 PrintMap((int*)map, N);
 Pos enrty = {2,0};
 stack<Pos> paths;
 cout<<endl;
 cout<<SearchMazePath((int*)map,N,enrty,paths);
 cout<<endl;
 PrintMap((int*)map, N);
 system("pause");
 return 0;
}