正确做法:
暴力枚举每一个点,再枚举该点上下左右四个点,若都存在则符合题目要求
进一步的枚举斜的四个点,得出答案
时间复杂度:o(n^3)
#include<iostream>
#include<vector>
using namespace std;
typedef pair<int ,int> PII;
int res[5];
int main(){
vector<PII> q;
int n;
cin>>n;
while(n--){
int x,y;
cin>>x>>y;
q.push_back(make_pair(x,y));
}
for(int i=0;i<q.size();i++){
int cnt=0;
int x=q[i].first,y=q[i].second;
for(int j=0,flag=0;j<q.size();j++){
if (q[j].first==x&&q[j].second==y+1)flag++;
if (q[j].first==x&&q[j].second==y-1)flag++;
if (q[j].first==x+1&&q[j].second==y)flag++;
if (q[j].first==x-1&&q[j].second==y)flag++;
if (flag==4){//代表满足题目要求的上下左右都存在垃圾
for(int k=0;k<q.size();k++){
if (q[k].first==x+1&&q[k].second==y+1)cnt++;
if (q[k].first==x-1&&q[k].second==y+1)cnt++;
if (q[k].first==x+1&&q[k].second==y-1)cnt++;
if (q[k].first==x-1&&q[k].second==y-1)cnt++;
}
res[cnt]++;
break;
}
}
}
for(int i=0;i<5;i++)cout<<res[i]<<endl;
return 0;
}
若开二维数组来维护图的关系则可以减少一重循环,时间复杂度为o(n^2),但后五个测试数据的点可能存在1e9附近的数,数组不能开那么大,故只能过一半的数据
原文:https://www.cnblogs.com/wyf-fighting/p/13436354.html