用堆栈实现迷宫问题，二维数组表示迷宫：1表示墙壁，0表示可以走的路，只能横着走或竖着走

不能斜着走，要求编程实现找到从左上角到右下角的路线

//深度优先：有解就退出搜索（不一定是最优解）#include<iostream>#include<stdio.h>usingnamespacestd;#defineROW5#defineCOL5typedefstructpoint{int_row;int_col;}Point;Pointstack[512];inttop=0;voidPush(Point&p){stack[top++]=p;}constPoint&Pop(){returnstack[--top];}intIsEmpty(){returntop==0;}intmaze[ROW][COL]={{0,0,0,0,0},{0,1,1,1,0},{0,1,1,0,0},{0,1,1,0,1},{0,0,0,0,0},};voidPrintMaze(){for(inti=0;i<ROW;++i){for(intj=0;j<COL;++j){cout<<maze[i][j]<<"";}cout<<endl;}cout<<endl;}PointPrev[ROW][COL]={{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},{{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},};voidVisit(introw,intcol,Point&p){Pointtmp={row,col};maze[row][col]=2;Prev[row][col]=p;Push(tmp);}voidTest1(){Pointp={0,0};maze[p._row][p._col]=2;Push(p);while(!IsEmpty()){p=Pop();if(p._row==ROW-1&&p._col==COL-1)break;//upif(p._row-1>=0&&maze[p._row-1][p._col]==0)Visit(p._row-1,p._col,p);//downif(p._row+1<ROW&&maze[p._row+1][p._col]==0)Visit(p._row+1,p._col,p);//leftif(p._col-1>=0&&maze[p._row][p._col-1]==0)Visit(p._row,p._col-1,p);//rightif(p._col+1<COL&&maze[p._row][p._col+1]==0)Visit(p._row,p._col+1,p);}if(p._row==ROW-1&&p._col==COL-1){printf("(%d,%d)\n",p._row,p._col);while((Prev[p._row][p._col])._row!=-1){p=Prev[p._row][p._col];printf("(%d,%d)\n",p._row,p._col);}}elsecout<<"nopath!\n";}

//广度求得最优路径，找到后停止搜索#include<iostream>usingnamespacestd;#defineROW5#defineCOL5typedefstructpoint{int_row;int_col;int_prev;}Point;Pointqueue[512];inthead=0;inttail=0;voidEnqueue(Point&p){queue[tail++]=p;}constPoint&Dequeue(){returnqueue[head++];}intIsEmpty(){returnhead==tail;}intmaze[ROW][COL]={{0,0,0,0,0},{0,1,1,1,0},{0,1,1,0,0},{0,1,1,0,1},{0,0,0,0,0},};voidPrintMaze(){for(inti=0;i<ROW;++i){for(intj=0;j<COL;++j){cout<<maze[i][j]<<"";}cout<<endl;}cout<<endl;}voidVisit(introw,intcol){Pointtmp={row,col,head-1};maze[row][col]=2;Enqueue(tmp);}voidTest1(){Pointp={0,0,-1};maze[p._row][p._col]=2;Enqueue(p);while(!IsEmpty()){p=Dequeue();if(p._row==ROW-1&&p._col==COL-1)break;//upif(p._row-1>=0&&maze[p._row-1][p._col]==0)Visit(p._row-1,p._col);//downif(p._row+1<ROW&&maze[p._row+1][p._col]==0)Visit(p._row+1,p._col);//leftif(p._col-1>=0&&maze[p._row][p._col-1]==0)Visit(p._row,p._col-1);//rightif(p._col+1<COL&&maze[p._row][p._col+1]==0)Visit(p._row,p._col+1);}if(p._row==ROW-1&&p._col==COL-1){printf("(%d,%d)\n",p._row,p._col);while(p._prev!=-1){p=queue[p._prev];printf("(%d,%d)\n",p._row,p._col);}}elsecout<<"nopath!\n";}