Ковшова бригада#10316

Ковшова бригада (Розбір)

Введемо систему координат. Наприклад, нехай верхній лівий кут має координати $(0, 0)$ . Знайдемо координати сараю $(b_{x}, b_{y})$ (b_x, b_y), озера $(l_{x}, l_{y})$ (l_x, l_y) та каменя $(r_{x}, r_{y})$ (r_x, r_y).

Далі знайдемо манхеттенські відстані:

$d_{B L} = B a r n L ak e$ d_{BL} = BarnLake — між сараєм та озером;
$d_{B R} = B a r n R oc k$ d_{BR} = BarnRock — між сараєм та каменем;
$d_{L R} = L ak e R oc k$ d_{LR} = LakeRock — між озером та каменем;

Манхеттенська відстань між об'єктами $A (x_{1}, y_{1})$ A(x_1, y_1) та $B (x_{2}, y_{2})$ B(x_2, y_2) обчислюється за формулою:

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

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

Якщо не враховувати камінь, то кількість корів у бригаді повинна дорівнювати манхеттенській відстані між сараєм та озером мінус один.

Необхідна кількість корів збільшується на $2$ лише в тому випадку, якщо сарай та озеро знаходяться на одній горизонтальній або вертикальній прямій, а камінь розташований на шляху між ними. Остання умова виконується, якщо:

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

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

Сарай та озеро знаходяться на одній горизонтальній прямій, якщо $b_{y} = l_{y}$ b_y = l_y.

Сарай та озеро знаходяться на одній вертикальній прямій, якщо $b_{x} = l_{x}$ b_x = l_x.

Приклад

Для заданого прикладу об'єкти мають наступні координати:

сарай $(3, 2)$ ,
озеро $(8, 5)$ ,
камінь $(5, 5)$

Манхеттенська відстань між сараєм та озером дорівнює $∣8 - 3∣ + ∣5 - 2∣ = 8$ | 8 - 3 | + | 5 - 2 | = 8. Необхідна кількість корів дорівнює $8 - 1 = 7$ 8 - 1 = 7.

Розглянемо наступний приклад, у якому камінь знаходиться між сараєм та озером. Відстань між сараєм та озером дорівнює $5$ . Без урахування каменя знадобиться $4$ корови. Однак, оскільки камінь перегороджує прямий шлях, для його обходу знадобиться додатково $2$ корови. Таким чином, загальна кількість корів становитиме $4 + 2 = 6$ 4 + 2 = 6.

Реалізація алгоритму

Читаємо вхідні дані. Розмір вхідного поля $10 \times 10$ 10 \times 10.

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

Знаходимо координати сараю $(b_{x}, b_{y})$ (b_x, b_y), озера $(l_{x}, l_{y})$ (l_x, l_y) та каменя $(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++

Обчислюємо наступні манхеттенські відстані:

$B a r n L ak e$ BarnLake — між сараєм та озером;
$B a r n R oc k$ BarnRock — між сараєм та каменем;
$L ak e R oc k$ LakeRock — між озером та каменем;

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

Знаходимо кількість $r es$ корів, необхідну для формування бригади між сараєм та озером. Вона на одиницю менша за манхеттенську відстань між точками $(b_{x}, b_{y})$ (b_x, b_y) та $(l_{x}, l_{y})$ (l_x, l_y).

res = BarnLake - 1;

Якщо сарай та озеро знаходяться на одній горизонталі або вертикалі, а камінь розташований на шляху між ними, то кількість корів, необхідну для побудови ланцюжка, слід збільшити на $2$ .

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

Виводимо відповідь.

cout << res << endl;