题解 | 小d和超级泡泡堂

由于炸弹可以直接把在同一个连通块杂草全清除，那么剩余不能被清除的就是不在同一个连通块的杂草，也就是被石头或边界包围着的杂草，也就是求我们所在连通块，尽可能去扩展，得到的杂草数量。

在实现上可以用BFS，然后由于每个点至多入队一次，至多出队一次，可以手写队列缩小一下常数。

#include <iostream>
#include <queue>
using namespace std;
const int N=1e6+7;
char a[1003][1003];
int n,m,x,y;
int dir[][2]={{0,1},{1,0},{-1,0},{0,-1}};
int ans=0;
pair<int,int> q[N];
int hh,tt=-1;
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]=='@'){
				x=i,y=j;
			}
		}
	}
	q[++tt]={x,y};
	while(hh<=tt){
		auto now=q[hh];
		hh++;
		for(int i=0;i<4;i++){
			int nx=now.first+dir[i][0];
			int ny=now.second+dir[i][1];
			if(nx>=1 && nx<=n && ny>=1 && ny<=m && a[nx][ny]!='#'){
				if(a[nx][ny]=='!')ans++;
				a[nx][ny]='#';
				q[++tt]={nx,ny};
			}
		}
	}
	cout<<ans;
	return 0;
}