程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> c++:迷宮問題的實現

c++:迷宮問題的實現

編輯:C++入門知識

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved