Delta-wave

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 9688 Accepted Submission(s): 3882

Problem Description

A triangle field is numbered with successive integers in the way shown on the picture below.

杭电ACM OJ 1030 Delta-wave 3维降2维坐标系法+图的搜索法

The traveller needs to go from the cell with number M to the cell with number N. The traveller is able to enter the cell through cell edges only, he can not travel from cell to cell through vertices. The number of edges the traveller passes makes the length of the traveller's route.

Write the program to determine the length of the shortest route connecting cells with numbers N and M.

Input

Input contains two integer numbers M and N in the range from 1 to 1000000000 separated with space(s).

Output

Output should contain the length of the shortest route.

Sample Input

6 12 

Sample Output

3

翻译：比如图中的6和12.如果你要从6走到12，必须是从边过去的。就是6-7-13-12 或者6-5-11-12不能从顶点一下子就过去了。

做法：这题有两种做法。1.用图的搜索，bfs搜索最短路径。2.找数学规律，发现是3维的坐标系。但是3维的坐标系比较复杂，于是在3维坐标系的基础上降成二维。

图的搜索：

我们画了一下路径，发现路径大致上是这样的。所以我们很轻易就能得知，用数据结构把这个图表示出来+BFS搜索最短路径就能轻松解决这个问题。

方法2:3维降二维坐标系法

我们不难得知，每个点都有3个方法可以走。所以可以建3维坐标系解决这个问题。但是3维坐标系太花时间，我们可以降成2维的。

我们把上下两个看成一个，就是二维的了。

为什么可以把上下两个看成一个？因为下面的数字可以很轻易地由上面的数字的得出来。比如1到3差值就是2.2到6差值就是4，4到8差值也是4.5到11差值是6，7到13差值也是6，9到15差值也是6.

接下来把二维数组列一下。

就是这样的，接下来再上一张图揭示规律。

我们假如要算21的坐标，那么我们怎么根据21这个值求出他的坐标呢？

我们发现 1和21的差值无非就是1 + 3 + 7 + 9

然而我们观察1到14 是1+5+7

所以我们知道了 横向相差的值是和纵坐标的值挂钩的 纵坐标每下一层 起始值就会大2

我们用算是来表示

纵向差值 1 + 3 + 5。。。。。2i-1 i个

横向差值 2i + 3 + 2i + 5 + 2i + 7 +。。。。2i + 2j + 1 j个

所以得出 纵向差值 + 横向差值 + 1 = 值

等差数列公式

得出

（i + j） * （i + j） + 2j = 值

我们只需要开for循环 找到两个值之间的坐标 进行 （x1 - x2） + (y1 - y2)就是结果

注意输入的值要进行处理 比如2 和 6 你输入的是6 把它转化成2再求

最后求完只是整体之间的步数 上下还要区分开来 

代码

void calculate(int a, int b) {
    int x1 = -1;
    int y1 = -1;

    int x2 = -1;
    int y2 = -1;

    for (int i = 0; i < 100; i ++) {
        for (int j = 0; j < 100; j ++) {
            if (a == 1 + (i + j) * (i + j) + 2 * j) {
                x1 = i;
                y1 = j;
            }

            if (b == 1 + (i + j) * (i + j) + 2 * j) {
                x2 = i;
                y2 = j;
            }
        }
    }

    int result = Math.abs(x1 - x2) + Math.abs(y1 - y2);

    System.out.println(result + "");
}

全部代码

package ACM1000_1099;

// TODO: 2017/12/3 方法1：图
// TODO: 2017/12/3 方法2：三维降二维坐标系

public class DeltaWave1030 {
    DeltaWave1030(int a, int b) {
        calculate(a, b);
    }

    void calculate(int a, int b) {
        int x1 = -1;
        int y1 = -1;

        int x2 = -1;
        int y2 = -1;

        for (int i = 0; i < 100; i ++) {
            for (int j = 0; j < 100; j ++) {
                if (a == 1 + (i + j) * (i + j) + 2 * j) {
                    x1 = i;
                    y1 = j;
                }

                if (b == 1 + (i + j) * (i + j) + 2 * j) {
                    x2 = i;
                    y2 = j;
                }
            }
        }

        int result = Math.abs(x1 - x2) + Math.abs(y1 - y2);

        System.out.println(result + "");
    }

    public static void main(final String[] args) throws Exception {
        DeltaWave1030 d = new DeltaWave1030(2, 12);
    }
}

杭电ACM OJ 1030 Delta-wave 3维降2维坐标系法+图的搜索法

Delta-wave

相关推荐