DFS：depth first search深度优先搜索（迷宫寻路） BFS：breadth first search宽度优先搜

#include<bits/stdc++.h> #include<queue> #include <stack> //#include "stdafx.h" using namespace std; struct point{ int x; int y; }; int **Maze; point **Pre; point movedir[8]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}; void Create(int row,int column) { 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) { if(x==row&&y==column) return true; queue<point>q; point now; now.x=x; now.y=y; q.push(now); Maze[now.x][now.y]=-1; while(!q.empty()) { now=q.front(); q.pop(); for(int i=0;i<8;i++) { if(now.x+movedir[i].x==row&&now.y+movedir[i].y==column) { Maze[now.x+movedir[i].x][now.y+movedir[i].y]=-1; Pre[row][column]=now; return true; } if( Maze[now.x+movedir[i].x][now.y+movedir[i].y]==0) { point temp; temp.x=now.x+movedir[i].x; temp.y=now.y+movedir[i].y; q.push(temp); Maze[now.x+movedir[i].x][now.y+movedir[i].y]=-1; Pre[ temp.x][ temp.y]=now; } } } return false; } void PrintPath(int row,int column) { point temp; queue<point>s; temp.x=row; temp.y=column; while(temp.x!=1||temp.y!=1) { s.push(temp); temp=Pre[temp.x][temp.y]; } //printf("(%d,%d) ",row,column); while(!s.empty()) { temp=s.front(); cout<<"("<<temp.x<<","<<temp.y<<")"<<endl; s.pop(); } cout<<"(1,1)"; // cout<<endl; } int main() { int row; int column; cin>>row>>column; Maze=new int *[row+2]; Pre=new point*[row+2]; for(int i=0;i<row+2;i++) { Maze[i]=new int[column+2]; Pre[i]=new point[column+2]; } Create(row,column); if(MazePath(row,column,1,1)) { // cout<<"YES"<<endl; PrintPath(row,column); } else { cout<<"NO"<<endl; } return 0; }