题目：
链接：https://ac.nowcoder.com/acm/contest/912/A来源：牛客网
垃圾小x经常在机房丢垃圾，比如奶茶杯子、用过的湿巾纸、吃完的零食包装等。
可是训练的桌子上放了电脑，实在放不下小x丢的垃圾了。因此，大家搬了一张专门丢垃圾的桌子放在小x边上。为了防止小x丢垃圾的时候溢出，这张桌子很大，可以用一个
105×105105×105的网格来表示，桌子的左上角视为格点(1,1)，右下角视为格点(105,105)(105,105)。 有了这么大的桌子，小x就可以肆意地丢垃圾：小x丢的垃圾既不会堆叠，也不会相邻（若两块垃圾在上下左右及斜对角方向有接触，则为相邻） 看着这么大的桌子被用来丢垃圾，你不禁发出了疑问：已知哪些格点被垃圾覆盖，那么小x一共丢了多少垃圾？
输入描述:
第一行一个正整数
n(1≤n≤106)n(1≤n≤106)，代表有几个格点被垃圾覆盖。接下来n行，每行两个正整数xi,yi(1≤xi,yi≤105)xi,yi(1≤xi,yi≤105)，代表格点(xi,yi)(xi,yi)被垃圾覆盖。
输出描述:
输出一行，一个正整数，代表小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这里直接dfs容易挂，巧妙用到set代码：#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;}
备注:
样例示意图如下（为了方便观察，格点之间留了空隙）
转载于:https://www.cnblogs.com/flyljz/p/10995115.html
