栈应用----迷宫问题

#pragma once //递归实现迷宫 #include <iostream> #include <assert.h> #include <stack> using namespace std; const size_t N=10; void InitMaze(int Maze[][N],size_t n) { FILE* fout=fopen("Rmap.txt","r"); assert(fout); for(size_t i=0;i<n;++i) { for(size_t j=0;j<n;) { char ch=fgetc(fout); if(ch=='0'||ch=='1') { Maze[i][j]=ch-'0'; j++; } } } fclose(fout); } void PrintMaze(int Maze[][N],size_t n) { for(size_t i=0;i<n;++i) { for(size_t j=0;j<n;++j) { cout<<Maze[i][j]<<" "; } cout<<endl; } cout<<endl; } struct Pos { size_t _row;//行 size_t _col;//列 }; bool CheckAccess(int Maze[][N],size_t n,Pos pos) { if((pos._row<n)&&(pos._row>=0) &&(pos._col<n)&&(pos._col>=0) &&(Maze[pos._row][pos._col]==0)) { return true; } return false; } bool GetMazeMapR(int Maze[][N],size_t n,Pos cur,stack<Pos>& Path,stack<Pos>& shortPath) { Path.push(cur); if(cur._row==n-1) { if(shortPath.empty()||Path.size()<shortPath.size()) { shortPath=Path; } return true;//若只想输出一条通路，则加上这句 } Maze[cur._row][cur._col]=2; Pos next; next=cur; next._row-=1;//上 if(CheckAccess(Maze,n,next)) { if(GetMazeMapR(Maze,n,next,Path,shortPath)) { return true; } } next=cur; next._col+=1;//右 if(CheckAccess(Maze,n,next)) { if(GetMazeMapR(Maze,n,next,Path,shortPath)) { return true; } } next=cur; next._row+=1;//下 if(CheckAccess(Maze,n,next)) { if(GetMazeMapR(Maze,n,next,Path,shortPath)) { return true; } } next=cur; next._col-=1;//左 if(CheckAccess(Maze,n,next)) { if(GetMazeMapR(Maze,n,next,Path,shortPath)) { return true; } } Path.pop(); return false; } #pragma once #include <iostream> #include <assert.h> #include <stack> using namespace std; const size_t N=10; void InitMaze(int Maze[][N],size_t n) { FILE* fout=fopen("map.txt","r"); assert(fout); for(size_t i=0;i<n;++i) { for(size_t j=0;j<n;) { char ch=fgetc(fout); if(ch=='0'||ch=='1') { Maze[i][j]=ch-'0'; j++; } } } fclose(fout); } void PrintMaze(int Maze[][N],size_t n) { for(size_t i=0;i<n;++i) { for(size_t j=0;j<n;++j) { cout<<Maze[i][j]<<" "; } cout<<endl; } cout<<endl; } struct Pos { size_t _row;//行 size_t _col;//列 }; bool CheckAccess(int Maze[][N],size_t n,Pos pos) { if((pos._row<n)&&(pos._row>=0) &&(pos._col<n)&&(pos._col>=0) &&(Maze[pos._row][pos._col]==0)) { return true; } return false; } bool GetMazeMap(int Maze[][N],size_t n,Pos entry) { stack<Pos> path; path.push(entry); while(!path.empty()) { Pos cur=path.top(); Pos next; Maze[cur._row][cur._col]=2; if(cur._row==n-1) { return true; } next=cur; next._row--;//上 if(CheckAccess(Maze,n,next)) { path.push(next); continue; } next=cur; next._col++;//右 if(CheckAccess(Maze,n,next)) { path.push(next); continue; } next=cur; next._row++;//下 if(CheckAccess(Maze,n,next)) { path.push(next); continue; } next=cur; next._col--;//左 if(CheckAccess(Maze,n,next)) { path.push(next); continue; } Pos pur=path.top();//回溯 Maze[pur._row][pur._col]=3; path.pop(); } return false; } #pragma once #include <iostream> #include <assert.h> #include <stack> #include <iomanip> using namespace std; const size_t N=10; struct Pos { size_t _row; size_t _col; }; void InitMaze(int Maze[][N],size_t n) { FILE* fout=fopen("Rmap.txt","r"); assert(fout); for(size_t i=0;i<n;++i) { for(size_t j=0;j<n;) { char ch=fgetc(fout); if(ch=='0'||ch=='1') { Maze[i][j]=ch-'0'; ++j; } } } } void PrintMaze(int Maze[][N],size_t n) { cout<<setw(3)<<setiosflags(ios::left); for(size_t i=0;i<n;++i) { for(size_t j=0;j<n;++j) { cout<<Maze[i][j]<<setw(3)<<setiosflags(ios::left);//默认的是在n个字符宽度中右对齐输出,setiosflags（iOS::left）设置为左对齐输出 } cout<<endl; } cout<<endl; } bool ChackAccess(int Maze[][N],size_t n,Pos cur,Pos next) { if((next._row<n)&&(next._row>=0) &&(next._col<n)&&(next._col>=0)) { if((Maze[next._row][next._col]==0)||(Maze[cur._row][cur._col]<Maze[next._row][next._col])) { return true; } } return false; } bool GetMazeMapMore(int Maze[][N],size_t n,Pos cur,stack<Pos>& Path,stack<Pos>& shortPath) { Path.push(cur); if(cur._row==n-1) { if(shortPath.empty()||Path.size()<shortPath.size()) { shortPath=Path; } } Pos next; next=cur; next._row-=1; if(ChackAccess(Maze,n,cur,next)) { Maze[next._row][next._col]=Maze[cur._row][cur._col]+1; if(GetMazeMapMore(Maze,n,next,Path,shortPath)) return true; } next=cur; next._col+=1; if(ChackAccess(Maze,n,cur,next)) { Maze[next._row][next._col]=Maze[cur._row][cur._col]+1; if(GetMazeMapMore(Maze,n,next,Path,shortPath)) return true; } next=cur; next._row+=1; if(ChackAccess(Maze,n,cur,next)) { Maze[next._row][next._col]=Maze[cur._row][cur._col]+1; if(GetMazeMapMore(Maze,n,next,Path,shortPath)) return true; } next=cur; next._col-=1; if(ChackAccess(Maze,n,cur,next)) { Maze[next._row][next._col]=Maze[cur._row][cur._col]+1; if(GetMazeMapMore(Maze,n,next,Path,shortPath)) return true; } Path.pop(); return false; }