AcWing 1855. 愤怒的奶牛(unordered_map+bfs)
原题链接
中等
作者:
来不及了
,
2022-02-22 15:49:17
,
所有人可见
,
阅读 167
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 110;
int n;
int a[N];
unordered_map<int,int> mp; //映射某个位置有没有干草捆
int bfs(int x)
{
//射向x这个位置
unordered_map<int,int> visited; //用来判断某个位置是否在队列之中
int t = 1; //爆炸半径
int res = 0;
queue<int> q;
q.push(x);
visited[x] = 1;
while(!q.empty())
{
int cnt = q.size(); //这一轮要进行遍历的个数
for (int i = 0; i < cnt; i ++ )
{
int temp = q.front();
q.pop();
res++;
int left = temp-t;
int right = temp+t;
for(int i=left;i<=right;i++) //枚举每个位置,如果没有访问就加入队列中
{
if(mp[i]&&!visited[i])
{
q.push(i);
visited[i] = 1;
}
}
}
t++;
}
return res;
}
int main()
{
cin>>n;
for (int i = 0; i < n; i ++ )
{
cin>>a[i];
mp[a[i]] = 1;
}
int res = 0;
for (int i = 0; i < n; i ++ )
{
res = max(res,bfs(a[i]));
}
cout<<res<<endl;
return 0;
}