小明找妹子（迷宫问题 最短路径bfs）

一.题目描述:

东东有一张地图，想通过地图找到妹纸。地图显示，0表示可以走，1表示不可以走，左上角是入口，右下角是妹纸，这两个位置保证为0。编写程序找出东东找到妹纸的最短路线。
详细题目如下：

二.思路：

本题主要考察bfs的用法 ，起点为（0，0），终点为（4，4），要求找到起点到终点的最短路径。只要将起点入队列，每次循环都将队列的头作为当前点，判断当前点的上下左右四个点，如果满足未到达过，无路障的条件，就将点入队列，再次进行循环，直到到达了（4，4）。最后从终点回溯路线到达起点，就可以输出小明的正确行进路线。

三.不同结构的用处

1.结构体点的类型
x为点的横坐标，y为纵坐标。将点设为point类型，便于入队列和栈。

struct point
{//结构体点 
 int x,y;
 point& operator=(point& pp)
 {
  x=pp.x;
  y=pp.y;
  return *this;
 }
}p;

2.不同作用的二维数组
a用0和1来区分能够走的路和路障，pre函数用来记录前驱节点，便于回溯；dx和dy是试探方向

int a[5][5];//迷宫数组 
int vis[5][5];//是否到达过 
point pre[5][5];//用来记录前驱节点 
int dx[4]={0,0,1,-1} ;//四个方向
int dy[4]={1,-1,0,0} ;

3.栈和队列
队列用在bfs，找到路径，栈用在从终点回溯记录路线上。

queue<point> sp;//队列 
stack<point> xp;//栈

四.完整代码

/*东东找妹子：迷宫，起点和终点固定，找出路线*/ 
#include<iostream>
#include<queue> 
#include<stack>
using namespace std;

struct point
{//结构体点 
	int x,y;
	point& operator=(point& pp)
	{
		x=pp.x;
		y=pp.y;
		return *this;
	}
}p;

int a[5][5];
int vis[5][5];
point pre[5][5];//用来记录前驱节点 
int dx[4]={0,0,1,-1} ;//四个方向
int dy[4]={1,-1,0,0} ;

queue<point> sp;//队列 
stack<point> xp;//栈

void bfs()
{
    vis[0][0]=1;
	while(!sp.empty())
	{
		point p1=sp.front() ;
		int x=p1.x;
		int y=p1.y;
	    sp.pop() ;	
	    
	 for(int i=0;i<4;i++)
	 {
		int xx=x+dx[i];
		int yy=y+dy[i];//移动后的点
		
		if(a[xx][yy]==0&&vis[xx][yy]==0&&xx>=0&&xx<=4&&yy>=0&&yy<=4) //此点未被到达过
		{
		vis[xx][yy]=1;//此时已被到达过 
		p.x=xx;
		p.y=yy;
		sp.push(p);//进队列 
		pre[xx][yy]=p1;//前驱节点记录 
		} 
		
	 }
	 if(x==4&&y==4)//到达终点 
	       break;
     }
	point p2;
	p2.x=4;
	p2.y=4;
	while(!(p2.x==0&&p2.y==0))//回溯，将点压入栈 
	{
		xp.push(p2);	
		p2=pre[p2.x][p2.y];
	}
	cout<<"("<<0<<","<<0<<")"<<endl;
	//输出 
	while(xp.size() >1 )
	{
		point p3=xp.top() ;
		xp.pop() ;
	    cout<<"("<<p3.x<<","<<p3.y<<")"<<endl;
	}
	cout<<"("<<4<<","<<4<<")";
	
} 


int main()
{
	
	for(int i=0;i<5;i++)
	  for(int j=0;j<5;j++)//数组a中存储迷宫信息
	  {cin>>a[i][j]; 
	  vis[i][j]=0;//是否到达过 
	   } 
	  
	p.x=0;
	p.y=0;
	sp.push(p);   
	bfs();
	  
	return 0;
}