信息
- ID
- 2825
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 49
- 已通过
- 13
- 上传者
给定一个 n×m 的矩阵,求与在 (x,y) 位置上的数相同的最近位置。
由于“最近”一词其实包含了距离+两个关键字的排序(即 x 和 y),所以使用 struct + sort + cmp 来解决。
但是排序有一个前置条件:数值相同。所以扫一遍,把数值相同的拎出来排序即可。
那么怎么排序呢?“最近”我们用距离来定义,“距离”在矩阵中一般用曼哈顿距离来定义。所以:
#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;
}