CCF-201912-2
今天就这个题目来复习一下STL-map别看图了，看看题目怎么说吧！解题思路使用STL-map的好处使用STL-map的注意点下面是解题代码最后是STL-map的API了
今天就这个题目来复习一下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;
}
嘻嘻！
最后是STL-map的API了
