7993题解(广度优先搜索)
2024-07-29 20:57:19
发布于:浙江
22阅读
0回复
0点赞
题目不难,过关的唯一难点在于读题。
由输入可知:小路的宽度、长度,以及瓷砖的排列。
我们应该从“第一块砖”开始,搜索所有能走到的砖,并计算出最多能走过的砖块数。
所以这是一道普通的深搜题,但是我喜欢用广搜来做。那么解题思路就显而易见了。
① 我们首先应该输入小路的宽度与长度。
② 字符输入小路上瓷砖的种类,并获取“第一块砖”的位置。
③ 使用广度优先搜索,搜索所有能走过的砖并计算数量。
④ 输出砖的数量。
一旦完整地写出了整道题的一种思路,就大胆去写代码吧。如果这种算法不能通过,我们再看看是否还有更好的算法。
//写注释写上瘾了!注释太多会不会有些难看(?)
#include <iostream>
#include <queue>
using namespace std;
char mapp[25][25];//地图
bool over[25][25];//表示是否已经走过某块瓷砖,防止重复计数。
int cnt=0;//走过的瓷砖数(答案)。
int w,h;
void BFS(int sx,int sy);//声明广搜函数
int main(){
int sx,sy;//表示起点的坐标(就是第一块砖的坐标)
cin >> w >> h;//此时h是行数,w是列数,不要把两者弄错。
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
cin >> mapp[i][j];//输入整个地图
if(mapp[i][j]=='@'){//如果遍历到第一块砖,就确定了起点的坐标了。
sx=i;sy=j;
}
}
}
BFS(sx,sy);//写到这里,假设我们的广搜函数已经写完,那么使用这个函数之后,
cout << cnt;//输出一下答案就ok了。
return 0;
}
//接下来还是到了写广搜函数的环节(悲)。由于你看的是我的题解,接下来的注释非 常 非 常 多 。
struct node{//定义一个结构体node来表示某个坐标。
int x,y;
};
int dx[4]={1,-1,0,0};//这两个数组是存放移动量的。
int dy[4]={0,0,1,-1};
void BFS(int sx,int sy){//定义深搜函数
queue <node> q;//定义一个类型为node的队列,用来存放待探索的瓷砖坐标。
q.push({sx,sy});//把起始点扔进里面。
cnt++;//起始点也算一块砖,所以计数器加1。
over[sx][sy]=1;//起始点不用被探索,所以标记已经被探索过!
while(!q.empty()){//如果队列空了,说明没有需要被探索的瓷砖了,停止搜索。
node now=q.front();//从队首获取信息
int x=now.x,y=now.y;
q.pop();//过河拆桥。
for(int i=0;i<4;i++){//向四个方向探索
int fx=x+dx[i],fy=y+dy[i];//记录向某个方向移动后会到达的坐标。
//这瓷砖啊,我有3不走!!!
if(over[fx][fy]==0 &&//1、走过的,我不走。因为我已经走过了,还走它干啥?
mapp[fx][fy]!='#' &&//2、不安全的,我不走。因为那样就死了。
fx>=1&&fy>=1&&fx<=h&&fy<=w)//3、超出边界的,我不走。因为我不想去后室。
{
over[fx][fy]=1;//标记我走了这块砖。
cnt++;//又多走了一块砖,计数器加1。
q.push({fx,fy});//继续把走到的瓷砖扔进里面。
}
}
}
}
我怎么又写了这么多注释?
经过测试,我们第一次写出的代码可以通过本道题的所有测试点。
这里空空如也
有帮助,赞一个