曼哈顿距离矩阵

曼哈顿距离矩阵

码题集OJ-曼哈顿距离矩阵 (matiji.net)

这道题主要是寻找规律然后总结出对应的表达式求解。

从图中可以看出数字的增加是一层一层增长，每次的增加量为4。在图中分别标出来每个象限的推导点。

我们有题目可知，我们需要求得的曼哈顿距离都是输入的（x,y)到原点（0,0）的距离刚好对应的是该点所在的层数。比如（2,1），Dist=|2-0|+|1-0|=3，（2,1)在第三层。

所以距离为Dist=|x|+|y|代码如下：

int Dist=abs(x)+abs(y)

然后寻找关系，(1,2)的值对应的是13,前两层的值的数量为(4+8)=12,所以13=x+12=1+12=13;

我们需要求到该层数前面所以层数的数字的数量量一共有多少。

for(int i=1;i<Dist;i++)
S+=4*i;//因为每层的数量都为4的倍数

可以得到在第一象限的值的表达式为S+x

if(x>0&&y>=0)
cout<<S+x<<'\n';//输出第一象限对应坐标的值

可以看出这道题就是为了推导坐标与Dist以及层数的关系，从而来得到对应坐标的填入的数字。

可以推导出第四象限：例子为(2，-1),Dist=3,S=12,填入的数字为16；可以知道16=12+4；

然后能够让两数相加得到4的只有Dist+(-y)=3+1=4;

所以可以得到第四象限填入数字的表达式为S+Dist+(-y);

if(x>=0&&y<0)
cout<<S+Dist+(-y)<<'\n';//输出第四象限对应坐标的值

其他象限的推导过程同样；

第三象限的表达式为S+2*(Dist)+(-x);

if(x<0&&y<=0)
cout<<S+2*Dist+(-x)<<'\n';//输出第三象限对应坐标的值

第二象限的表达式为S+3*(Dist)+y;

if(x<=0&&y>0)
cout<<S+3*Dist+y<<'\n';//输出第二象限对应坐标的值

完整的代码入下：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int x,y,S;
	cin>>x>>y;
	int Dist=abs(x)+abs(y);
	for(int i=1;i<Dist;i++)
		S+=4*i;
	if(Dist==0)
		cout<<0<<'\n';//输入为(0,0)
	if(x>0&&y>=0)
		cout<<S+x<<'\n';//输出第一象限对应坐标的值
	else if(x<=0&&y>0)
		cout<<S+3*Dist+y<<'\n';//输出第二象限对应坐标的值
	else if(x<0&&y<=0)
		cout<<S+2*Dist+(-x)<<'\n';//输出第三象限对应坐标的值
	else if(x>0&&y<0)
		cout<<S+Dist+(-y)<<'\n';//输出第四象限对应坐标的值
return 0;
}

作为萌新想记录学习C++的生活，希望提出一些建议，感谢！