CCF-201912-2

今天就这个题目来复习一下STL-map

别看图了，看看题目怎么说吧！

解题思路

看到题目，最先想到的就是简单的bfs，其实我挺喜欢这种搜索的题，仔细点就能做出来，我们可以开一个大大的满足数据范围的二维数组，全部置零，然后输入的点对应的位置置1，表示这个点有人居住并把点记住。
输入完毕后，把记住的点全部拿出来。进行判断
1.上下左右的点都是1，那么这是个合格的垃圾站。
2.如果合格，我们要找到垃圾站的级别，这个时候，左上，右上，左下，右下每一个1，级别就+1，那么级别最低是0，最高是4。
3.我们假设这个级别是i，那么结果ans[i]++;
最后，用for循环打出ans的值就可以了
其实你可以发现，有几个不好的地方：
1.开数组，有很多地方没用上，消耗了内存
2.还要用结构体存点，其实和前面置1有点重复的感觉

使用STL-map的好处

map的查询可以用count()和find()，所以用来查询是很方便的。
本题由于不需要使用到二维数组的全部点，和复杂的图bfs有区别，那么，我们使用map来存点，就节约了很多内存了。

使用STL-map的注意点

1.map中如果使用到了结构体，结构体中需要写一个排序规则
2.find()如果没找到就会返回end()
3.map的参数调用为first，second，然后iterator是循环调用的关键字

下面是解题代码

#include<iostream>
#include<cstring>
#include<map>
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node{
    int x;
    int y;
    node(int a,int b){
      x=a;
      y=b;
    }
    bool operator < (const node a)const{
      if(a.x!=x) return a.x<x;
      else return a.y<y;
    }
};
map<node,int> m;
int xway[4]={0,0,1,-1};
int yway[4]={1,-1,0,0};
int xx[4]={1,1,-1,-1};
int yy[4]={1,-1,1,-1};
int check(node a){
    for(int i=0;i<4;i++){
      int nx=a.x+xway[i];
      int ny=a.y+yway[i];
      if(m.find(node(nx,ny))==m.end()){
             return 0;
        }
    }
    for(int i=0;i<4;i++){
      int nx=a.x+xx[i];
      int ny=a.y+yy[i];
      if(m.find(node(nx,ny))!=m.end()) m[a]++;
    }
    return 1;
}
int main(){
    int n;
    cin>>n;
    int ans[5];
    mm(ans,0);
    while(n--){
      int x,y;
      cin>>x>>y;
      m[node(x,y)]=0;
    }
    for(map<node,int>::iterator it=m.begin();it!=m.end();it++){
      if(check(it->first)){
            ans[it->second]++;
        }
    }
    for(int i=0;i<5;i++){
      cout<<ans[i]<<endl;
    }
    return 0;
}