February 22, 2018

# 題目

You have to lead a pack of ants in search of food. The ants have to march through a rather large brick wall. They need to ensure that they are not on the surface of the bricks as it gets easier for mean people to crush them. If they can travel through the valleys, it would be much harder to kill them.
The bricks are laid out in a regular grid like pattern (as shown in the figure). Each brick is a rectangle that is 2 units long horizontally and 1 unit long vertically. There are tiny gaps (valleys) in between two bricks (both horizontally and vertically).
The ants are to start at a point in the valley, and their destination is a point in the valley as well. As the bricks are of fixed size and are following a regular pattern with gaps, these points can always be represented by integer coordinates. Your task is to find the distance of the shortest path from the starting point to the destination point.

Input
There can be at most 1000 test cases. Each test case consists of four integers giving the values of starting row Sr , starting column Sc , destination row Dr , destination column Dc . You can assume that 1 ≤ Sr, Sc, Dr, Dc ≤ $$10^9$$. The last line of input will be ‘0 0 0 0’ — this line must not be processed as a test case.

Output
For each test case print the distance of the shortest path in a single line.

Sample Input

1 7 2 7
5 4 3 2
2 3 3 6
0 0 0 0


Sample Output

1
4
4


# 程式碼

## C++

#include <algorithm>
#include <iostream>

#include <climits>

// the core of this problem
int64_t calc_shortest_distance(int64_t src_row, int64_t src_col, int64_t dest_row, int64_t dest_col);

// read input from stdin
// return true if read from stdin successfully else false
bool read_input(int64_t& src_row, int64_t& src_col, int64_t& dest_row, int64_t& dest_col);

// check is it all zero
inline bool is_end(int64_t src_row, int64_t src_col, int64_t dest_row, int64_t dest_col)
{ return src_row == 0 and src_col == 0 and dest_row == 0 and dest_col == 0; }

// for output answer
inline void output(int64_t distance) { std::cout << distance << std::endl; }

constexpr const int ABS_SHIFT_LL = sizeof(int64_t) * CHAR_BIT - 1;
// return the absolute value of a
inline int64_t _abs(int64_t a)
{
int64_t mask = a >> ABS_SHIFT_LL;
return (a + mask) ^ mask;
}

// return -1 if 'a' is negative else 1
inline int sign(int64_t a) { if (a >> 63) return -1; else return 1; }

// start
int main()
{
int64_t src_row, src_col, dest_row, dest_col;
while (true)
{
// read input from stdin
if (!read_input(src_row, src_col, dest_row, dest_col)) break;

// if give input "0 0 0 0" then break
if (is_end(src_row, src_col, dest_row, dest_col)) break;

// calc the shortest path and print
output(calc_shortest_distance(src_row, src_col, dest_row, dest_col));
}
return 0;
}

int64_t calc_shortest_distance(int64_t src_row, int64_t src_col, int64_t dest_row, int64_t dest_col)
{
int64_t distance = 0;

// variables for storing difference of source and destination
int64_t diff_row = dest_row - src_row, diff_col = dest_col - src_col;

// variables for storing current position
int64_t current_row = src_row, current_col = src_col;

// diagonally move
int64_t diagonal = std::min(_abs(diff_row), _abs(diff_col));
current_row += diagonal * sign(diff_row);
current_col += diagonal * sign(diff_col);
distance += diagonal * 2;

diff_col = dest_col - current_col;

// if they're on the same column
if (diff_col) distance += _abs(diff_col);
else
{
// calculate the distance of the repeating pattern
diff_row = dest_row - current_row;
int64_t rows = _abs(diff_row) / 2;
distance += rows * 4;
current_row += rows * 2 * sign(diff_row);

diff_row = dest_row - current_row;

// if they're not arrived yet
if (diff_row)
// if the row and the column are both odd or both even numbers
if ((current_row & 1) == (current_col & 1))
if (diff_row > 0) distance += 1;
else distance += 3;
else
if (diff_row > 0) distance += 3;
else distance += 1;
}

return distance;
}

bool read_input(int64_t& src_row, int64_t& src_col, int64_t& dest_row, int64_t& dest_col)
{
if (std::cin >> src_row >> src_col >> dest_row >> dest_col)
return true;
//  src_row = src_col = dest_row = dest_col = 0; // comment it since it's not necessary
return false;
}