小d和超级泡泡堂【牛客tracker 每日一题】
小d和超级泡泡堂
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
小D DD在某天醒来发现自己穿越到了小游戏《超级泡泡堂》的世界，他得到了一份地图，一个技能和三个提示。
这个地图共有n nn行m mm列，行从上到下按1 ˜ n 1 \~\ n1˜n编号，列从左到右按1 ˜ m 1 \~\ m1˜m编号。地图上存在空地、石头、杂草。
这个技能是在自己当前所在位置放置一个不会对自己造成影响的炸弹，炸弹爆炸会产生火焰，火焰会向上下左右四个方向蔓延，如果火焰的蔓延方向上为空地，则会直接蔓延到空地并且在空地上开始继续蔓延，如果火焰的蔓延方向上为杂草，则会将杂草烧掉使其变为空地， 并且在新产生的空地继续蔓延，如果火焰蔓延方向上为石头，则无法继续朝这个方向蔓延，当然，火焰不可能蔓延到地图外。
三个提示分别是:
1、你可以向上下左右四个方向移动，如果那个方向上不是石头且不会移动到地图外。
2、你的技能只能使用一次。
3、你只有正确回答你最多能通过使用技能使多少杂草地变为空地才能够回到现实世界。
小D DD非常想要回去现实世界玩原神，请你帮助他计算出他最多能通过使用技能使多少杂草地变为空地。
注:当火焰蔓延到另一个地方将要继续蔓延时，蔓延方式等同于在该地方重新放置炸弹。注😗当火焰蔓延到另一个地方将要继续蔓延时，蔓延方式等同于在该地方重新放置炸弹。
输入描述：
第一行包含两个整数n , m ( 1 ≤ n , m ≤ 1000 ) n,m(1≤n,m≤1000)n,m(1≤n,m≤1000)。
接下来n nn行每行m mm个字符，其中′ . ′ '.'′.′表示空地，′ # ′ '\#'′#′表示石头，‘ ! ′ ‘!'‘!′表示杂草，‘ @ ’ ‘@’‘@’表示小D DD当前所处位置。
输出描述：
输出一行包含一个整数表示他最多能通过使用技能使多少杂草地变为空地。
示例1
输入：
4 4 ..!. .@.# !##! #!!!输出：
2解题思路
本题核心是通过广度优先搜索（BFS）模拟小D DD可移动范围及炸弹火焰蔓延效果，因火焰蔓延规则与小D DD移动规则一致（仅石头阻挡，杂草可被烧掉变为空地继续蔓延），故只需先找到小D DD的初始位置，再从该位置出发进行B F S BFSBFS：遍历上下左右四个方向，若位置在地图内、未被访问且非石头，则标记为已访问；若该位置是杂草，统计数量加1 11；将所有合法位置入队继续扩展。最终统计的杂草数量即为使用技能最多能变为空地的杂草地数量，该方法时间复杂度为O ( n × m ) O(n×m)O(n×m)，适配n 、 m ≤ 1000 n、m≤1000n、m≤1000的规模，通过B F S BFSBFS完整覆盖所有可蔓延区域，精准统计可烧毁的杂草总数。
总结
- 核心逻辑：火焰蔓延规则等价于小D DD的移动规则，通过B F S BFSBFS遍历所有可到达（可蔓延）区域。
- 关键操作：遍历过程中统计遇到的杂草数量，即为技能可烧毁的杂草地总数。
- B F S BFSBFS的边界条件：地图范围内、未访问、非石头，确保仅处理合法的蔓延区域。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<ll,ll>pii;constll N=1e3+10;constll p=1e9+7;chara[N][N];ll vis[N][N];ll dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};intmain(){ll n,m,sx,sy,cnt=0;cin>>n>>m;for(ll i=1;i<=n;i++){for(ll j=1;j<=m;j++){cin>>a[i][j];if(a[i][j]=='@')sx=i,sy=j;}}queue<pair<ll,ll>>qu;qu.push({sx,sy});vis[sx][sy]=1;while(!qu.empty()){pair<ll,ll>cur=qu.front();qu.pop();for(ll i=0;i<4;i++){ll dx=cur.first+dir[i][0],dy=cur.second+dir[i][1];if(dx>=1&&dx<=n&&dy>=1&&dy<=n&&!vis[dx][dy]&&a[dx][dy]!='#'){if(a[dx][dy]=='!')cnt++;qu.push({dx,dy});vis[dx][dy]=1;}}}cout<<cnt<<endl;return0;}