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;
}



分享给朋友:
您可能感兴趣的文章:
随机阅读: