通过长逝,暴力不用任何优化也就是O(n4)的复杂度可以得到20pts,然后我尝试了哈希表的做法如下
#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
struct node
{
int x,y;
};
int n,m;
unordered_map<int,vector<node>>mp;
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
int num;
cin>>num;
mp[num].push_back({i,j});
}
}
int ans=0;
for(const auto &p:mp)
{
const auto &v=p.second;
for(int i=0;i<v.size();i++)
{
for(int j=i+1;j<v.size();j++)
{
int x1=v[i].x,y1=v[i].y;
int x2=v[j].x,y2=v[j].y;
if(abs(x1-x2)==abs(y1-y2)&&abs(x1-x2)>0)
{
ans++;
}
}
}
}
cout<<ans*2;
return 0;
}
但很明显这个复杂度是O(n3)只能得到40pts,各位dalao能不能优化一下