当前位置:网站首页>走出迷宫的最少步数2
走出迷宫的最少步数2
2022-08-09 23:46:00 【-JMY-】
题目描述
当你站在一个迷宫里的时候,往往会被错综复杂的道路弄得失去方向感,如果你能得到迷宫地图,事情就会变得非常简单。假设你已经得到了一个n*m的迷宫的图纸,请你找出从起点到出口的最短路。
输入
第一行是两个整数n和m(1<=nm<=100),表示迷宫的行数和列数。接下来n行,每行一个长为m的字符串,表示整个迷宫的布局。字符'.'表示空地,'#'表示墙,'S'表示起点'T'表示出口。
输出
输出从起点到出口最少需要走的步数。
样例输入
3 3 S#T .#. ...
样例输出
6
参考代码:
#include<bits/stdc++.h>
using namespace std;
int n,m;
int q[5000][2],hh,tt,kx,ky,l,gx,gy;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int d[50][50];
char a[50][50];
void bfs(){
while(hh!=tt){
kx=q[hh][1];
ky=q[hh][0];
hh++;
for(int i=0;i<4;i++){
int xx=kx+dx[i];
int yy=ky+dy[i];
if(xx>=0&&xx<m&&yy>=0&&yy<n&&a[yy][xx]!='#'&&d[yy][xx]==0){
tt++;
q[tt-1][0]=yy;
q[tt-1][1]=xx;
d[yy][xx]=d[ky][kx]+1;
}
}
}
return;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>a[i][j];
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
if(a[i][j]=='S'){
q[0][0]=i;
q[0][1]=j;
d[i][j]=1;
}
if(a[i][j]=='T'){
gx=j;
gy=i;
}
}
tt++;
bfs();
cout<<d[gy][gx]-1;
return 0;
}
边栏推荐
猜你喜欢
随机推荐
2022金九银十工作潮,怎么样才能成功跳槽面试拿到高薪呢?
Alibaba Cloud SMS Service Activation
Copper's emotion
快速响应性智能型/智能响应性聚乙二醇纳米/还原响应型水凝胶的研究与制备
CST Studio Suite 2021 software installation package and installation tutorial
生成树和交换的总结
2022中高级Android面试题汇总来助你通过面试
知行合一的时候
Tensor flow 踩坑记
MATLB|和她跌宕起伏最终到达人生之峰【浪漫旅途】
03|流程控制
技术分享 | 接口自动化测试如何处理 Header cookie
Creo5.0 introductory tutorial free material
YOLOV5 study notes (7) - training your own data set
Biotin-Cy2 Conjugate,生物素-Cy2 偶联物_Cy2 生物素偶联物
[NCTF2019]True XML cookbook-1|XXE漏洞
WPF DataGrid using data templates
Fury:一个基于JIT动态编译的高性能多语言原生序列化框架
拒绝“重复造轮子”,百度EasyDL让你玩转AI定制开发
LSTM-based distributed energy generation prediction (Matlab code implementation)