AcWing 1219. 移动距离
原题链接
简单
作者:
ICSERM
,
2024-03-14 15:21:50
,
所有人可见
,
阅读 15
移动距离
分析
- 时间复杂度:排号最多也就10000;数据范围很小;
- 模拟分析一下长度为w的矩阵中,第i个号的位置;为了避免不必要的特判,我们把所有坐标映射到以0开始的矩阵中。所以m–, n–;
- 位置分为x, y;取值范围是0~w-1;注意,这里的x是从上往下,y是从左往右;
- i/w是x的值;
- y的值,分两种情况讨论:如果x是偶数,则y是从左往右顺序排列,如果x是奇数,则y逆序排列;
- 若x是偶数:y%w
- 若x是奇数:w -1 - y%w
- 最短移动距离,曼哈顿距离:
distance = abs(x1-x2) + abs(y1-y2)
代码
#include <iostream>
using namespace std;
const int N = 10010;
int map[N][N], w, m, n;
int x1, y1, x2, y2;
void coordinate(int &x, int &y, int i){
x = i/w;
x%2 ? y = w - 1 - i%w : y = i%w;
}
int main(){
cin >> w >> m >> n;
coordinate(x1, y1, m-1), coordinate(x2, y2, n-1);
cout << abs(x1-x2)+abs(y1-y2) << endl;
return 0;
}