欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

试题E:迷宫

程序员文章站 2022-05-16 09:14:00
...

试题E:迷宫试题E:迷宫

题目如上图所示,代码:

#include<bits/stdc++.h>
using namespace std;
int array[100][100],v[100][100];
struct point
{
	int x;
	int y;
	int step;
};
queue<point> r;//用STL里面的模板开一个队列  
int dx[4]={0,1,0,-1};//四个方向 右,下,左,上 
int dy[4]={1,0,-1,0}; 
int main()
{
	int m,n;
	cin>>m>>n;//迷宫m行,n列 
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			cin>>array[i][j];//输入有无障碍 有:1,无:0
	int startx,starty,p,q;
	cin>>startx>>starty>>p>>q;//输入起点的坐标,终点的坐标 
	//BFS:
	point start;//定义一个起点 并赋值
	start.x=startx;
	start.y=starty;
	start.step=0;
	r.push(start);//将起点入队
	v[startx][starty]=1;//标志数组设置起点为已被访问
	int flag=0;//用来判断能否走到终点 
	
	while(!r.empty()) //当队列不为空 
	{
		int x=r.front().x,y=r.front().y;//取出队首元素 
		if(x==p&&y==q)//到达终点 
		{
			flag=1; 
			cout<<r.front().step;
			break;
		}
		for(int k=0;k<=3;k++)//k表示上下左右(顺时针) 
		{
			int tx,ty;//临时拓展方向 
			tx=x+dx[k];//当前队首元素加偏移 
			ty=y+dy[k];
			if(array[tx][ty]==0&&v[tx][ty]==0)//当前位置是空地且未访问
			{
				//入队
				point temp;//拓展的点 放temp里 
				temp.x=tx;
				temp.y=ty;
				temp.step=r.front().step+1;
				r.push(temp);
				v[tx][ty]=1; //设置为已访问
			} 
		}
		r.pop();//拓展完 将队首元素出队	
	}
	if(flag==0)
	 cout<<"No answer!"<<endl;
	return 0;  	
}
相关标签: 2019蓝桥杯省赛