Catena di secchi#10316

Catena di secchi (Editoriale)

Introduciamo un sistema di coordinate. Ad esempio, supponiamo che l'angolo superiore sinistro abbia coordinate $(0, 0)$ . Troviamo le coordinate del fienile $(b_{x}, b_{y})$ (b_x, b_y), del lago $(l_{x}, l_{y})$ (l_x, l_y) e della roccia $(r_{x}, r_{y})$ (r_x, r_y).

Di seguito troviamo le distanze di Manhattan:

$d_{B L} = B a r n L ak e$ d_{BL} = BarnLake — tra il fienile e il lago;
$d_{B R} = B a r n R oc k$ d_{BR} = BarnRock — tra il fienile e la roccia;
$d_{L R} = L ak e R oc k$ d_{LR} = LakeRock — tra il lago e la roccia;

La distanza di Manhattan tra gli oggetti $A (x_{1}, y_{1})$ A(x_1, y_1) e $B (x_{2}, y_{2})$ B(x_2, y_2) si calcola con la formula:

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

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

Se non si tiene conto della roccia, il numero di mucche nella squadra deve essere pari alla distanza di Manhattan tra il fienile e il lago meno uno.

Il numero richiesto di mucche aumenta di $2$ solo nel caso in cui il fienile e il lago si trovino sulla stessa retta orizzontale o verticale, e la roccia sia posizionata sul percorso tra di essi. Quest'ultima condizione è soddisfatta se:

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

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

Il fienile e il lago si trovano sulla stessa retta orizzontale se $b_{y} = l_{y}$ b_y = l_y.

Il fienile e il lago si trovano sulla stessa retta verticale se $b_{x} = l_{x}$ b_x = l_x.

Esempio

Per l'esempio dato, gli oggetti hanno le seguenti coordinate:

fienile $(3, 2)$ ,
lago $(8, 5)$ ,
roccia $(5, 5)$

La distanza di Manhattan tra il fienile e il lago è pari a $∣8 - 3∣ + ∣5 - 2∣ = 8$ | 8 - 3 | + | 5 - 2 | = 8. Il numero richiesto di mucche è pari a $8 - 1 = 7$ 8 - 1 = 7.

Consideriamo il seguente esempio, in cui la roccia si trova tra il fienile e il lago. La distanza tra il fienile e il lago è pari a $5$ . Senza tenere conto della roccia sarebbero necessarie $4$ mucche. Tuttavia, poiché la roccia blocca il percorso diretto, per superarla saranno necessarie $2$ mucche aggiuntive. Pertanto, il numero totale di mucche sarà $4 + 2 = 6$ 4 + 2 = 6.

Implementazione dell'algoritmo

Leggiamo i dati di input. La dimensione del campo di input è $10 \times 10$ 10 \times 10.

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

Troviamo le coordinate del fienile $(b_{x}, b_{y})$ (b_x, b_y), del lago $(l_{x}, l_{y})$ (l_x, l_y) e della roccia $(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++

Calcoliamo le seguenti distanze di Manhattan:

$B a r n L ak e$ BarnLake — tra il fienile e il lago;
$B a r n R oc k$ BarnRock — tra il fienile e la roccia;
$L ak e R oc k$ LakeRock — tra il lago e la roccia;

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

Troviamo il numero $r es$ di mucche necessario per formare la squadra tra il fienile e il lago. Esso è inferiore di uno rispetto alla distanza di Manhattan tra i punti $(b_{x}, b_{y})$ (b_x, b_y) e $(l_{x}, l_{y})$ (l_x, l_y).

res = BarnLake - 1;

Se il fienile e il lago si trovano sulla stessa orizzontale o verticale, e la roccia è posizionata sul percorso tra di essi, allora il numero di mucche necessario per costruire la catena deve essere aumentato di $2$ .

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

Stampiamo la risposta.

cout << res << endl;