A83468题解
2026-08-14 19:18:29
发布于:浙江
31阅读
0回复
0点赞
背景:
原题链接
我个人认为本题表述不清,没有说清是四方向还是八方向,我试了一下是四方向,大家按四方向写代码即可。(本人已反馈)
思路:
广搜模板题,用队列实现,建立四方向数组,在队列里放入起始点,并遍历把方向,如果没有越界并没有访问,且不是障碍物,就加入队列。最后,看看终点有没有被访问,访问过就输出,没有输出。
代码:
#include <iostream>
#include <queue>
using namespace std;
int n,m;
int sx,sy,fx,fy;
char mp[50][50];//地图
bool vis[50][50];//访问数组
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//四方向数组
int main(){
cin>>n>>m;
cin>>sx>>sy>>fx>>fy;//输入
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
cin>>mp[i][j];
}
}//输入地图
queue<pair<int,int>>q;//pair储存x,y
q.push({sx,sy});//放入队列
vis[sx][sy]=1;//标记初始点(不要忘!!!)
while (q.size()){
pair<int,int>k=q.front();
q.pop();//弹出队首
for (int i=0;i<4;i++){//四方向遍历
int nx=k.first+dir[i][0];
int ny=k.second+dir[i][1];//新的节点
if (nx>=1&&nx<=n&&ny>=1&&ny<=m&&vis[nx][ny]==0&&mp[nx][ny]!='#'){//没有越界并没有访问,且不是障碍物
vis[nx][ny]=1;//标记(不要忘!!!)
q.push({nx,ny});//入队
}
}
}//广度优先搜索
if (vis[fx][fy]==1){//是否访问过
cout<<"YES";
}else{
cout<<"NO";
}//输出
return 0;
}
结语:
希望对大家学习OI有帮助!
这里空空如也








有帮助,赞一个