小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的边界条件地图范围内、未访问、非石头确保仅处理合法的蔓延区域。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpairll,llpii;constll N1e310;constll p1e97;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,cnt0;cinnm;for(ll i1;in;i){for(ll j1;jm;j){cina[i][j];if(a[i][j])sxi,syj;}}queuepairll,llqu;qu.push({sx,sy});vis[sx][sy]1;while(!qu.empty()){pairll,llcurqu.front();qu.pop();for(ll i0;i4;i){ll dxcur.firstdir[i][0],dycur.seconddir[i][1];if(dx1dxndy1dyn!vis[dx][dy]a[dx][dy]!#){if(a[dx][dy]!)cnt;qu.push({dx,dy});vis[dx][dy]1;}}}coutcntendl;return0;}