经典迷宫问题DFS
给定一个迷宫，入口为左上角，出口为右下角，问是否有路径从入口到出口，若有则输出一条这样的路径。注意移动可以从上、下、左、右、上左、上右、下左、下右八个方向进行。迷宫输入0表示可走，输入1表示墙。易得可以用1将迷宫围起来避免边界问题。
本题采用DFS算法给出解。
/*迷宫问题（八方向）input:16 80 1 1 1 0 1 1 11 0 1 0 1 0 1 00 1 0 0 1 1 1 10 1 1 1 0 0 1 11 0 0 1 1 0 0 00 1 1 0 0 1 1 0output:YES(1,1) (2,2) (3,1) (4,1) (5,2) (5,3) (6,4) (6,5) (5,6) (4,5) (4,6) (5,7) (5,8) (6,8) （递归）(1,1) (2,2) (3,3) (3,4) (4,5) (5,6) (5,7) (6,8) （栈）*/#include<iostream>#include<stack>using namespace std;struct point{ int x; int y;};int **Maze;stack<point> sp;point move[8]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};void Create(int row,int column){ //创建迷宫，注意到用0表示可走，1表示墙，将整个输入的迷宫再用墙围着，处理的时候就不用特别注意边界问题 int i,j; for(i=0; i<row+2; i++)Maze[i][0] = Maze[i][column+1] = 1; for(j=0; j<column+2; j++)Maze[0][j] = Maze[row+1][j] = 1; for(i=1; i<=row; i++){ for(j=1; j<=column; j++){ cin>>Maze[i][j]; } }}/*bool MazePath(int row,int column,int x,int y){ //判断是否有路径从入口到出口，保存该路径（递归） Maze[x][y] = -1; point temp; temp.x = x; temp.y = y; sp.push(temp); for(int i=0; i<8; i++){ if(x + move[i].x == row && y + move[i].y == column)return true; if(Maze[x + move[i].x][y + move[i].y] == 0){ if(MazePath(row,column,x + move[i].x,y + move[i].y))return true; } } sp.pop(); return false;}*/bool MazePath(int row,int column,int x,int y){ //判断是否有路径从入口到出口，保存该路径（栈） stack<point> save; bool flag; point now; now.x = x; now.y = y; save.push(now); while(!save.empty()){ now = save.top(); if(Maze[now.x][now.y] == 0){ sp.push(now); Maze[now.x][now.y] = -1; } flag = true; for(int i=0; i<8; i++){ if(now.x + move[i].x == row && now.y + move[i].y == column)return true; if(Maze[now.x + move[i].x][now.y + move[i].y] == 0){ point temp; temp.x = now.x + move[i].x; temp.y = now.y + move[i].y; save.push(temp); flag = false; } } if(flag){ save.pop(); sp.pop(); } }}void PrintPath(int row,int column){ //输出从入口到出口的路径 point temp; temp.x = row; temp.y =column; stack<point> pp; pp.push(temp); while(!sp.empty()){ temp = sp.top(); sp.pop(); pp.push(temp); } while(!pp.empty()){ temp = pp.top(); cout<<'('<<temp.x<<','<<temp.y<<')'<<' '; pp.pop(); } cout<<endl;}int main(){ int t,row,column; cin>>t; while(t--){ cin>>row>>column; Maze = new int*[row + 2]; for(int i=0; i<row+2; i++)Maze[i] = new int[column + 2]; Create(row,column);if(MazePath(row,column,1,1)){ cout<<"YES"<<endl; PrintPath(row,column);}else cout<<"NO"<<endl; } return 0;}