C++利用循環(huán)和棧實現(xiàn)走迷宮
本文實例為大家分享了C++利用循環(huán)和棧實現(xiàn)走迷宮的具體代碼,供大家參考,具體內(nèi)容如下
要求:
1、將地圖的數(shù)組保存在文件中,從文件中讀取行列數(shù)
2.、動態(tài)開辟空間保存地圖
3.、運行結(jié)束后再地圖上標出具體的走法
說明:
1、文件中第一行分別放置的是地圖的行數(shù)和列數(shù)
2、其中1表示墻,即路不通,0表示路,即通路
3、程序運行結(jié)束后用2標記走過的路徑
4、當走到“死胡同”時用3標記此路為死路
5、每到一個點,按照 左 上 右 下 的順序去試探
6、沒有處理入口就是"死胡同"的極端情況
地圖文件截圖:
代碼示例:maze.h
#ifndef _MAZE_H_ #define _MAZE_H_ #include <stack> #include <fstream> // ifstream #include <iostream> #include <string> using namespace std; // 坐標類 class Seat { public: Seat(int _x, int _y) :x(_x) ,y(_y) { } int x; int y; }; // 迷宮類 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: // 開始走 bool PassMaze(stack<Seat>& s, Seat& entry); // 打印地圖 void PrintMap(); // 析構(gòu) 釋放空間 ~Maze(); }; #endif
maze.cpp
// 迷宮之遞歸實現(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ù) 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對應的十進制值減去 } a_line++; // 向后移動指針 } ++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; } // 開始走 void Maze::PassMaze( Seat& entry) { stack<Seat> s; if (IsPass(entry)) { s.push(entry); // 壓棧當前位置 while (!s.empty()) // 棧不為空繼續(xù) { Seat curSeat = s.top(); // 取得棧頂存儲的位置 // 走到邊界 if (curSeat.x < 0 || curSeat.y < 0 || entry.y >= _col || entry.x >= _row ) { return; } _map[curSeat.x][curSeat.y] = 2; // 將走過的路標記為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; } // 運行到此處說明 每個方向都沒有路可走 是死路標記為3 _map[curSeat.x][curSeat.y] = 3; // 出棧這個“死路位置” 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)造一個迷宮對象 m1.PrintMap(); // 走之前打印 m1.PassMaze(Seat(9, 4)); //開始走 傳遞迷宮入口點 m1.PrintMap(); // 結(jié)束后再次打印 return 0; }
截圖:
以上就是本文的全部內(nèi)容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
C++數(shù)據(jù)結(jié)構(gòu)之堆詳解
本文詳細講解了C++數(shù)據(jù)結(jié)構(gòu)之堆,文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-04-04C++/Php/Python 語言執(zhí)行shell命令的方法(推薦)
下面小編就為大家?guī)硪黄狢++/Php/Python 語言執(zhí)行shell命令的方法(推薦)。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2017-03-03C++中對象的常引用、動態(tài)建立和釋放相關(guān)知識講解
這篇文章主要介紹了C++中對象的常引用、動態(tài)建立和釋放相關(guān)知識講解,是C++入門學習中的基礎知識,需要的朋友可以參考下2015-09-09