#ifndef _MAZE_H_ 
#define _MAZE_H_ 
 
#include <stack>    
#include <fstream>  // ifstream 
#include <iostream> 
#include <string> 
using namespace std; 
 
// 坐標(biāo)類(lèi) 
class Seat 
{ 
public: 
  Seat(int _x, int _y) 
    :x(_x) 
    ,y(_y) 
  {  } 
  int x; 
  int y; 
}; 
 
// 迷宮類(lèi) 
 
class Maze 
{ 
private: 
  int** _map; // 指向地圖的指針 
  int _row; // 存放地圖的行數(shù) 
  int _col; // 存放地圖的列數(shù) 
public: 
  // 構(gòu)造函數(shù) 讀取文件里的地圖 和行數(shù) 
  Maze(const string& filePath); 
 
private: 
  // 判斷是否是路 
  bool IsPass(Seat& entry); 
 
public: 
  // 開(kāi)始走 
  bool PassMaze(stack<Seat>& s, Seat& entry); 
 
  // 打印地圖 
  void PrintMap(); 
 
  // 析構(gòu) 釋放空間 
  ~Maze(); 
}; 
#endif 

// 迷宮之遞歸實(shí)現(xiàn) 
#include "maze.h" 
 
// 構(gòu)造函數(shù) 
Maze::Maze(const string& filePath) 
{ 
  ifstream mapFile(filePath, ofstream::out); 
  assert(mapFile); // 斷言文件是否存在 
  string str_row_col; //第一行 獲取行和列 
  string str_temp; // 臨時(shí)字符串  
 
  // 獲取行列的個(gè)數(shù) 
  getline(mapFile,str_row_col);// 讀取第一行 
  str_temp = str_row_col.substr(0, str_row_col.find_first_of(','));// 取得字符串中的字串獲取行數(shù) 
  _row = atoi(str_temp.c_str()); // atoi將字符串轉(zhuǎn)為數(shù)字 
  str_temp = str_row_col.substr(str_row_col.find_first_of(',')+1); // 取得字符串中的列數(shù) 
  _col = atoi(str_temp.c_str()); // atoi將字符串轉(zhuǎn)為數(shù)字 
 
  // 分配空間 
  _map = new int*[_row];  
  for (int idx = 0; idx < _col; ++idx) 
  { 
    _map[idx] = new int[_col]; 
  } 
   
 
  // 填充地圖 
  int index_row = 0; // 放置地圖 二維數(shù)組的行索引 
  int index_col = 0; // 放置地圖 二維數(shù)組的列索引 
  while (!mapFile.eof()) 
  { 
    getline(mapFile, str_temp); 
    char* a_line = (char*)str_temp.c_str(); 
    // 遍歷一行 
    while (*a_line != '\0') 
    { 
      if (*a_line == '0' || *a_line == '1') 
      { 
        _map[index_row][index_col++] = *a_line - '0'; // 減0 是將字符'0'的 ASCII對(duì)應(yīng)的十進(jìn)制值減去 
      } 
      a_line++; // 向后移動(dòng)指針 
    } 
    ++index_row; 
    index_col = 0; // 每處理完一行后將列索引置0 
  } 
  mapFile.close(); 
} 
 
  // 判斷是否是路 
bool Maze::IsPass(Seat& entry) 
{ 
  if (entry.x < 0 || entry.y < 0 || entry.y >= _col || entry.x >= _row) 
  { 
    return true; 
  } 
  if (_map[entry.x][entry.y] == 0) 
  { 
    return true; 
  } 
  return false; 
} 
 
 
// 開(kāi)始走 
void Maze::PassMaze( Seat& entry) 
{ 
  stack<Seat> s; 
  if (IsPass(entry)) 
  { 
    s.push(entry); // 壓棧當(dāng)前位置 
    while (!s.empty()) // 棧不為空繼續(xù) 
    { 
      Seat curSeat = s.top(); // 取得棧頂存儲(chǔ)的位置 
      // 走到邊界 
      if (curSeat.x < 0 || curSeat.y < 0 || entry.y >= _col || entry.x >= _row ) 
      { 
        return; 
      } 
      _map[curSeat.x][curSeat.y] = 2; // 將走過(guò)的路標(biāo)記為2 
 
      // 往左走 
      Seat left(curSeat.x, curSeat.y-1); 
      if (IsPass(left)) 
      { 
        s.push(left);  
        continue; 
      } 
      // 往上走 
      Seat up(curSeat.x-1, curSeat.y); 
      if (IsPass(up)) 
      { 
        s.push(up); 
        continue; 
      } 
      // 往右走 
      Seat right(curSeat.x, curSeat.y+1); 
      if (IsPass(right)) 
      { 
        s.push(right); 
        continue; 
      } 
      // 往下走 
      Seat down(curSeat.x+1, curSeat.y); 
      if (IsPass(down)) 
      { 
        s.push(down); 
        continue; 
      } 
 
      // 運(yùn)行到此處說(shuō)明 每個(gè)方向都沒(méi)有路可走 是死路標(biāo)記為3 
      _map[curSeat.x][curSeat.y] = 3; 
      // 出棧這個(gè)“死路位置” 
      s.pop(); 
    } 
  } 
} 
 
// 打印地圖 
void Maze::PrintMap() 
{ 
  for (int index_row = 0; index_row < _row; ++index_row) 
  { 
    for (int index_col = 0; index_col < _col; ++index_col) 
    { 
      cout << _map[index_row][index_col] <<" "; 
    } 
    cout <<endl; 
  } 
  cout <<endl; 
} 
 
// 析構(gòu) 
Maze::~Maze() 
{ 
  for (int idx = 0; idx < _row; ++idx ) 
  { 
    delete[] _map[idx]; 
  } 
  delete[] _map; 
  _map = NULL; 
} 

test.cpp
[cpp] view plain copy
int main() 
{ 
  Maze m1("map.txt"); // 構(gòu)造一個(gè)迷宮對(duì)象 
  m1.PrintMap();  // 走之前打印 
  m1.PassMaze(Seat(9, 4)); //開(kāi)始走 傳遞迷宮入口點(diǎn) 
  m1.PrintMap(); // 結(jié)束后再次打印 
  return 0; 
}