懒洋洋找朋友 题解

题目大意

给定一个 $n \times m$ 的矩阵，求与在 $(x,y)$ 位置上的数相同的最近位置。

思路分析

由于“最近”一词其实包含了距离+两个关键字的排序（即 $x$ 和 $y$），所以使用 struct + sort + cmp 来解决。

但是排序有一个前置条件：数值相同。所以扫一遍，把数值相同的拎出来排序即可。

那么怎么排序呢？“最近”我们用距离来定义，“距离”在矩阵中一般用曼哈顿距离来定义。所以：

1. 先计算与点 $(x,y)$ 数值相等的点与 $(x,y)$ 之间的曼哈顿距离并储存。
2. 按照距离、$x$、$y$ 的值进行多关键字升序排序。
3. 取排完后的第一个即可。

代码

#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define IL inline
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;

int a[200][200];

struct node
{
	int x, y, step;
}p[N];

bool cmp(node a, node b)
{
    // 按照距离、x、y 的值进行多关键字升序排序。
	if (a.step != b.step) return a.step < b.step; // 距离升序排序
	else if (a.x != b.x) return a.x < b.x; // x升序排序
	return a.y < b.y;// y升序排序
    //如果都相同，放前放后无所谓。
}
int main()
{
    //输入部分
	int n, m;
	cin >> n >> m;
	int x, y;
	cin >> x >> y;
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= m;j++)
		{
			cin >> a[i][j];
		}
	}
	int len = 0;//光标初始化
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= m;j++)
		{
			if (a[i][j] == a[x][y])//筛出点 (x,y) 数值相等的点
			{
				if (x != i || y != j)//如果不是 (x,y) 这个点本身
				{
					p[++len] = (node){i, j, abs(i - x) + abs(j - y)};//存储距离、x、y。
                    /*
                    	++len：光标右移一格
                    	abs(i - x) + abs(j - y)：(i,j)到(x,y)的曼哈顿距离
                    */
				}
			}
		}
	}
	sort(p + 1, p + len + 1, cmp); //排序
	cout << p[1].x << " " << p[1].y << endl;//取第一个输出
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <iomanip>
#include <cmath>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <fstream>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define ULLI unsigned long long int
const int N = 1e6+6;
const int INF = 0x3f3f3f3f;
int a[200][200];
struct node{
	int x,y,step;
}p[N];
bool cmp(node a,node b){
	if (a.step != b.step) return a.step < b.step;
	else if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}
int main(){
	int n,m;
	cin >> n >> m;
	int x,y;
	cin >> x >> y;
	for (int i = 1;i<=n;i++){
		for (int j = 1;j<=m;j++){
			cin >> a[i][j];
		}
	}
	int len = 0;
	for (int i = 1;i<=n;i++){
		for (int j = 1;j<=m;j++){
			if (a[i][j] == a[x][y]){
				if (x != i || y != j){
					p[len++] = (node){i,j,abs(i - x) + abs(j - y)};
				}
			}
		}
	}
	sort(p,p+len,cmp);
	cout << p[0].x << " " << p[0].y << endl;
    return 0;
}