题目描述

acwing1219. 移动距离

思路

首先按照蛇形1  2  3  4  5  6
        12 11 10 9  8  7
        13 14 15 .....
存储数组st[100010][100010];
找出m,n中的最大值，记为maxx=max(m,n);
其实只需要存储从1到maxx就可以了，存多了2重循环会爆。
因此存储maxx/w+1行即可。
其次，循环找出m,n对应的坐标（x1,y1）和（x2,y2）;
最后，计算最短移动距离，即abs(x1-x2)+abs(y1-y2);

算法1

(暴力枚举) $O(n^2)$

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int st[10010][10010];
int main(){
    int w,m,n;
    cin>>w>>m>>n;
    int maxx=max(n,m);
    int hh=maxx/w+1;
    int k=1;
    for(int i=1;i<=hh;i++)
    {
        if(i%2==1)
        {
         for(int j=1;j<=w;j++)
         {
             st[i][j]=k;
             k++;
         }
        }else{
            for(int j=w;j>0;j--)
            {
                st[i][j]=k;
                k++;
            }
        }
    }
    int x1=0,y1=0,x2=0,y2=0;
    for(int i=1;i<=hh;i++)
    for(int j=1;j<=w;j++)
    {
        if(st[i][j]==m)x1=i,y1=j;
        if(st[i][j]==n)x2=i,y2=j;
    }
     cout<<abs(x1-x2)+abs(y1-y2);
    return 0;
}