NC26106. Rubbish
描述
输入描述
第一行一个正整数，代表有几个格点被垃圾覆盖。
接下来n行，每行两个正整数，代表格点
被垃圾覆盖。
输出描述
输出一行，一个正整数，代表小x共丢了多少块垃圾。
示例1
输入:
15 1 1 2 2 1 2 3 4 4 3 4 4 6 6 6 4 6 5 3 7 2 1 5 6 3 3 4 6 4 7
输出:
2
C++11(clang++ 3.9) 解法, 执行用时: 3136ms, 内存消耗: 101764K, 提交时间: 2019-06-09 22:07:07
#include<iostream>
#include<set>
using namespace std;
set<pair<int,int> >st;
int a[8]={0,0,1,1,1,-1,-1,-1};
int b[8]={1,-1,-1,0,1,-1,0,1};
void dfs(int x,int y)
{
st.erase(make_pair(x,y));
for(int i=0;i<8;i++)
if(st.find(make_pair(x+a[i],y+b[i]))!=st.end())
dfs(x+a[i],y+b[i]);
}
int main()
{
int x,y,n,ans=0;
cin>>n;
while(n--)
{
cin>>x>>y;
st.insert(make_pair(x,y));
}
set<pair<int,int> >::iterator it;
while(!st.empty())
{
it=st.begin();
x=it->first;
y=it->second;
dfs(x,y);
ans++;
}
cout<<ans<<endl;
return 0;
}