[UVa] 13271 - Brick Walls

題目

Link: UVa 13271 - Brick Walls

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

Hint

這個題目只是找規律而已,算是一個間單的題目。

我的方法是先斜著走,走到跟終點同一行或是同一列之後,
再看要橫著走還是豎著走。

程式碼

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;
}

Show Comments