Bucket Brigade#10316

Bucket Brigade (Editorial)

Let us introduce a coordinate system. For example, let the top-left corner have coordinates $(0, 0)$ . Find the coordinates of the barn $(b_{x}, b_{y})$ (b_x, b_y), the lake $(l_{x}, l_{y})$ (l_x, l_y), and the rock $(r_{x}, r_{y})$ (r_x, r_y).

Next, compute the following Manhattan distances:

$d_{B L} = B a r n L ak e$ d_{BL} = BarnLake — the distance between the barn and the lake;
$d_{B R} = B a r n R oc k$ d_{BR} = BarnRock — the distance between the barn and the rock;
$d_{L R} = L ak e R oc k$ d_{LR} = LakeRock — the distance between the lake and the rock;

The Manhattan distance between two points $A (x_{1}, y_{1})$ A(x_1, y_1) and $B (x_{2}, y_{2})$ B(x_2, y_2) is computed using the following formula:

d_{A B} = ∣ x_{2} - x_{1} ∣ + ∣ y_{2} - y_{1} ∣

d_{AB} = | x_2 - x_1 | + | y_2 - y_1 |

If we ignore the rock, the number of cows in the bucket brigade should be equal to the Manhattan distance between the barn and the lake minus one.

The required number of cows increases by $2$ only if the barn and the lake lie on the same horizontal or vertical line, and the rock is located between them. The latter condition is satisfied if:

d_{B L} = d_{B R} + d_{L R}

d_{BL} = d_{BR} + d_{LR}

The barn and the lake lie on the same horizontal line if $b_{y} = l_{y}$ b_y = l_y.

The barn and the lake lie on the same vertical line if $b_{x} = l_{x}$ b_x = l_x.

Example

For the given example, the objects have the following coordinates:

barn $(3, 2)$ ,
lake $(8, 5)$ ,
rock $(5, 5)$

The Manhattan distance between the barn and the lake is $∣8 - 3∣ + ∣5 - 2∣ = 8$ | 8 - 3 | + | 5 - 2 | = 8. Therefore, the required number of cows is $8 - 1 = 7$ 8 - 1 = 7.

Now consider an example where the rock lies between the barn and the lake. The distance between the barn and the lake is $5$ . Without considering the rock, $4$ cows would be required. However, since the rock blocks the direct path, $2$ additional cows are needed to go around it. Thus, the total number of cows is $4 + 2 = 6$ 4 + 2 = 6.

Algorithm implementation

Read the input data. The size of the input field is $10 \times 10$ 10 \times 10.

for (i = 0; i < 10; i++)
  cin >> s[i];

Find the coordinates of the barn $(b_{x}, b_{y})$ (b_x, b_y), the lake $(l_{x}, l_{y})$ (l_x, l_y), and the rock $(r_{x}, r_{y})$ (r_x, r_y).

for (i = 0; i < 10; i++)
for (j = 0; j < 10; j++)
{
  if (s[i][j] == 'R') { rx = i; ry = j; }
  if (s[i][j] == 'B') { bx = i; by = j; }
  if (s[i][j] == 'L') { lx = i; ly = j; }
}

C++

Compute the following Manhattan distances:

$B a r n L ak e$ BarnLake — the distance between the barn and the lake;
$B a r n R oc k$ BarnRock — the distance between the barn and the rock;
$L ak e R oc k$ LakeRock — the distance between the lake and the rock;

BarnLake = abs(bx - lx) + abs(by - ly);
BarnRock = abs(bx - rx) + abs(by - ry);
LakeRock = abs(lx - rx) + abs(ly - ry);

Find the number of cows $r es$ needed to form the bucket brigade between the barn and the lake. It is one less than the Manhattan distance between the points $(b_{x}, b_{y})$ (b_x, b_y) and $(l_{x}, l_{y})$ (l_x, l_y).

res = BarnLake - 1;

If the barn and the lake are on the same horizontal or vertical line, and the rock is located between them, the number of cows needed to form the bucket brigade should be increased by $2$ .

if ((BarnLake == BarnRock + LakeRock) && (bx == lx || by == ly)) 
  res += 2;

Print the answer.

cout << res << endl;