c++：迷宮問題的實現
Maze.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stack>
using namespace std;
#define N 10 //定義數組大小
struct Pos{ //定義結構體保存路徑的坐標
size_t _row; //行
size_t _col; //列
};
stack <Pos> minstack; //定義最短路徑棧
void InitMaze(int maze[][N],int size){ //初始化迷宮
FILE* fout = fopen("MazeMap.txt", "r");
if (NULL == fout){
cout << "open Mazemap fail" << endl;
exit(-1);
}
for (int i = 0; i < size; ++i){
for (int j = 0; j < size;){
char ch = fgetc(fout);
if (ch == EOF){
cout << "init Mazemap fail" << endl;
exit(-1);
}
if (ch == '1' || ch == '0'){
maze[i][j] = ch - '0';
++j;
}
}
}
fclose(fout);
}
void DisplayMaze(int maze[][N],int size){ //顯示迷宮
for (int i = 0; i < size; ++i){
for (int j = 0; j < size; ++j){
cout << maze[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
bool CheckIsAccess(int maze[][N],Pos next){ //檢查是1還是0
if (next._col >= 0 && next._col <= N
&& next._row >= 0 && next._row <= N
&&maze[next._row][next._col] == 0){
return true;
}
return false;
}
bool GetMazePath(int maze[][N],Pos entry,stack<Pos>& path){ //找到通路
path.push(entry);
maze[entry._row][entry._col] = 2;
while (!path.empty()){
Pos cur = path.top();
Pos next = cur;
if (cur._row == N - 1 || cur._row == 0 || cur._col == N - 1 ){ //更新最短路徑
if (minstack.empty())
minstack = path;
else if (path.size() < minstack.size()){
minstack = path;
path.pop();
continue;
}
}
//up
next._row -= 1;
if (CheckIsAccess(maze, next)){
path.push(next);
maze[next._row][next._col] = 2;
continue;
}
next = cur;
//down
next._row += 1;
if (CheckIsAccess(maze, next)){
path.push(next);
maze[next._row][next._col] = 2;
continue;
}
next = cur;
//left
next._col -= 1;
if (CheckIsAccess(maze, next)){
path.push(next);
maze[next._row][next._col] = 2;
continue;
}
next = cur;
//right
next._col += 1;
if (CheckIsAccess(maze, next)){
path.push(next);
maze[next._row][next._col] = 2;
continue;
}
path.pop();
}
if (path.empty()) //判斷是否找完所有路徑
return true;
return false;
}
int main(){
int mazeMap[N][N] = { 0 };
InitMaze(mazeMap, N);
DisplayMaze(mazeMap, N);
stack<Pos> path;
Pos entry = {2,0}; //定義迷宮入口
bool ret = GetMazePath(mazeMap,entry,path);
if (ret){
cout << "succeed to get out" << endl;
DisplayMaze(mazeMap, N);
cout << "the shortest path is" << endl;
while (!minstack.empty()){
cout << "<" << minstack.top()._row << "," << minstack.top()._col << ">" << "<-";
minstack.pop();
}
}
return 0;
}
