UVA 10022 (Delta-wave)

题目：

解题思路： 找数学规律即可，有很多方法都可以。

代码：

/*
 *******************************************************************************
 *
 * Filename: 10022.cpp
 *
 * Description:
 *
 * Author: Ye Xiaofeng , yexfeng # gmail.com
 *
 *******************************************************************************
 */

#include <iostream>
#include <sstream>
#include <cmath>

using namespace std;

typedef unsigned int uint;

struct Item {
    Item(uint value);
    uint v_level;
    int h_level;
    bool up;
};

uint calc_dis(Item& item1, Item& item2)
{
    Item tmp_item = item2;
    uint distance = 0;
    while (tmp_item.v_level != item1.v_level) {
        if (tmp_item.up) {
            tmp_item.v_level--;
            tmp_item.up = false;
        } else {
            if (tmp_item.h_level < item1.h_level) {
                tmp_item.h_level++;
                tmp_item.up = true;
            } else {
                tmp_item.h_level--;
                tmp_item.up = true;
            }
        }
        distance++;
    }

    distance += abs(float(item1.h_level - tmp_item.h_level));
    return distance;
}

int main()
{
    int case_num = 0;
    stringstream ss;
    cin >> case_num;
    char line_buffer[40];

    cin.getline(line_buffer, 40);
    cin.getline(line_buffer, 40);
    uint v1, v2;
    uint path = 0;
    for (; case_num != 0; case_num--) {
        cin.getline(line_buffer, 40);
        while (line_buffer[0] != '\0') {
            ss.clear();
            ss << line_buffer;
            ss >> v1 >> v2;

            Item item1(v1);
            Item item2(v2);
            if (item1.v_level < item2.v_level) {
                path = calc_dis(item1, item2);
            } else {
                path = calc_dis(item2, item1);
            }
            cout << path << endl;
            cin.getline(line_buffer, 40);
        }
        if (case_num > 1) {
            cout << endl;
        }
    }
}

Item::Item(uint value)
{
    uint level = 1;
    while (1) {
        if (1+(level-1)*(level-1) > value) {
            break;
        }
        level++;
    }

    v_level = level-1;

    uint right = (level-1)*(level-1);
    uint left = 1+(level-2)*(level-2);

    uint middle = (left+right)/2;
    h_level = value-middle;
    if (0 == (value-left)%2) {
        up = false;
    } else {
        up = true;
    }
}