这是“Wishare杯”南邮第十一届大学生程序设计竞赛网络赛的C题。

Description:

如图为一个三角迷宫,迷宫中的数字从1开始标号。现给出两个数字m、n,请求出从m到n的最短路径,输出路径长度。

注:如图所示,迷宫中的数字被网格线所分隔,我们规定,穿过一次网格线,路径长度加一,初始路径长度为0。

1555125122634

Input:

第一行,一个整数T(0≤T≤1e6)。

接下来T行,每行两个整数,m、n(1≤m,n≤1e9​​)。

Output:

输出T行,每行一个整数,表示结果。

Sample Input:

1
6 12

Sample Output:

3

可惜我太菜了,用简单的分类讨论完成了这道题。

该图可以转化成一个自顶向下的组织关系图, row表示上下移动的次数,col表示左右移动的次数。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

long long getrow(long long num){
    long long sqrtnum = (long long)sqrt(num);
    for(long long i = 1;i <= sqrtnum+1;i++){
        if(num <= i*i){
            return i;
        }
    }
}

long long getdiffcol(long long m,long long n){
    long long diffrow = getrow(n) - getrow(m);
    long long diffcol;
    diffcol = fabs(n - (m + diffrow * getrow(m) * 2 + diffrow * (diffrow - 1)));
    if(diffcol >= diffrow){
        return diffcol;
    }else{
        if(getrow(m)%2 == m%2){
            diffcol += ((diffrow - diffcol - 1) / 2 + (diffrow - diffcol - 1) % 2) * 2;
        }else{
            diffcol += ((diffrow - diffcol) / 2 + (diffrow - diffcol) % 2) * 2;
        }
    }
    return diffcol;
}

int main(){
    long long t,m,n,diffrow,diffcol;
    scanf("%lld", &t);
    while(t--){
        scanf("%lld%lld",&m,&n);
        if(m > n){
            swap(m,n);
        }
        diffrow = getrow(n) - getrow(m);
        diffcol = getdiffcol(m,n); 
        printf("%lld\n",diffrow + diffcol);
    }
    return 0;
}