描述:
天天有一个大小为n×m的表格,行数从1到n,列数从1到m,每个单元格都有一个颜色,可以用1到105的整数来表示。
我们把位于第i行第j列的格子表示为(i,j),并将2个格子的距离定义为dis=abs(i2−i1)+abs(j2−j1),即曼哈顿距离
例如,在3×4表中,(1,2)和(3,3)之间的曼哈顿距离为3,其表示如下。(1,2)(2,2)(2,3)(3,3)。
天天决定计算每一对相同颜色(用数字表示颜色,相同数字即相同颜色)的单元格之间的曼哈顿距离之和。请你帮助他计算这个总和。
输入:
第一行包含两个整数n和m(1≤n≤m,n⋅m≤100000)表示行数和列数。
接下来的n行描述表格中的一行。第 i 行包含m 个整数Ci1,Ci2,...,Cim(1≤Cij≤100)表示第 i 行中单元格的颜色。
输出:
一个整数,表示每对相同颜色的单元格之间的曼哈顿距离之和。
注释:
输入
2 3
1 2 3
3 2 1
输出
7
输入
3 4
1 1 2 2
2 1 1 2
2 2 1 1
输出
76
备注
在第一个样本中,有三对相同颜色的单元格:单元格(1,1)和(2,3),单元格(1,2)和(2,2),单元格(1,3)和(2,1)。它们之间的曼哈顿距离分别是3、1和3,所以总和是7。
#include
#include
#include
#include
using namespace std;
typedef struct pos
{
int r;
int c;
struct pos *next=nullptr;
}pos;
unordered_map<int,pos*> g;
pos* notinlist(int rr,int cc)//如果不在字典中
{
pos *p=(pos*)malloc(sizeof(pos));
p->r=rr;
p->c=cc;
p->next=nullptr;
return p;
}
void* inlist(pos *p,int rr,int cc)//如果在字典中
{
while(p->next!=nullptr)
{
p=p->next;
}
pos *temp=(pos *)malloc(sizeof(pos));
temp->r=rr;
temp->c=cc;
temp->next=nullptr;
p->next=temp;
}
void addpos(int color,int rr,int cc)//加入字典操作
{
if(g.find(color)==g.end())//如果不存在字典中
{
pos *p=notinlist(rr,cc);
g.emplace(color,*p);
}
else
{
pos *p=g.at(color);
inlist(p,rr,cc);
}
}
int main()
{
int n,m;
int color;
cin>>n>>m;
for(int i=0;ifor(int j=0;j>color;
addpos(color,i,j);
}
}
int ans=0;
for(auto iter=g.begin();iter!=g.end();++iter)
{
while(iter->second->next!=nullptr)
{
pos*stk=iter->second;
pos*stk2=stk->next;
while(stk->next!=nullptr||stk2==nullptr)
{
ans+=abs(stk->r-stk2->r)+abs(stk->c-stk2->c);
stk2=stk2->next;
}
}
}
cout<system("pause");
return 0;
}
error: no matching function for call to 'std::pair
将每个出现的数字加入unordered_map作为键,然后值为一个指针,该指针指向一个链表储存了该建所有出现过的坐标
得出答案