试题E:迷宫
程序员文章站
2022-05-16 09:14:00
...
试题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;
}
下一篇: 刚跟媳妇儿交往那会儿
推荐阅读
-
迷宫问题
-
Codeforces Round #340 (Div. 2)-E-XOR and Favorite Number(莫队)
-
面试题查找婴儿同名频率和数量(并查集,代码超时了)
-
联想ThinkPad E431&E531 开机出现0190报错现象的解决方案详细介绍
-
2018最新前端面试题三
-
Linux下科学计数法(e)转化为数字的方法
-
Python面试题之这两个参数是什么意思:*args,**kwargs?我们为什么要使用它们?
-
E - Okabe and Boxes
-
Educational Codeforces Round 41 (Rated for Div. 2) E. Tufurama(树状数组+偏序)
-
PHP递归创建多级目录(一道面试题的解题过程)