Vedrə briqadası#10316

Vedrə briqadası (Həll təhlili)

Koordinat sistemi quraq. Məsələn, sol yuxarı küncün koordinatları $(0, 0)$ olsun. Tövlənin $(b_{x}, b_{y})$ (b_x, b_y), gölün $(l_{x}, l_{y})$ (l_x, l_y) və daşın $(r_{x}, r_{y})$ (r_x, r_y) koordinatlarını tapaq.

Sonra Manhettən məsafələrini tapaq:

$d_{B L} = B a r n L ak e$ d_{BL} = BarnLake — tövlə ilə göl arasında;
$d_{B R} = B a r n R oc k$ d_{BR} = BarnRock — tövlə ilə daş arasında;
$d_{L R} = L ak e R oc k$ d_{LR} = LakeRock — göl ilə daş arasında;

$A (x_{1}, y_{1})$ A(x_1, y_1) və $B (x_{2}, y_{2})$ B(x_2, y_2) obyektləri arasındakı Manhettən məsafəsi aşağıdakı düsturla hesablanır:

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

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

Daşı nəzərə almasaq, briqadadakı inəklərin sayı tövlə ilə göl arasındakı Manhettən məsafəsindən bir vahid az olmalıdır.

Tələb olunan inək sayı yalnız o halda $2$ vahid artır ki, tövlə və göl eyni üfüqi və ya şaquli düz xəttdə yerləşsin, daş isə onların arasındakı yolda olsun. Sonuncu şərt aşağıdakı halda ödənilir:

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

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

Tövlə və göl eyni üfüqi xəttdədir, əgər $b_{y} = l_{y}$ b_y = l_y.

Tövlə və göl eyni şaquli xəttdədir, əgər $b_{x} = l_{x}$ b_x = l_x.

Nümunə

Verilmiş nümunə üçün obyektlərin koordinatları aşağıdakı kimidir:

tövlə $(3, 2)$ ,
göl $(8, 5)$ ,
daş $(5, 5)$

Tövlə ilə göl arasındakı Manhettən məsafəsi $∣8 - 3∣ + ∣5 - 2∣ = 8$ | 8 - 3 | + | 5 - 2 | = 8-ə bərabərdir. Tələb olunan inək sayı $8 - 1 = 7$ 8 - 1 = 7-dir.

İndi isə daşın tövlə ilə göl arasında yerləşdiyi növbəti nümunəyə baxaq. Tövlə ilə göl arasındakı məsafə $5$ -dir. Daşı nəzərə almasaq, $4$ inək tələb olunacaq. Lakin daş düz yolu bağladığından, onun ətrafından keçmək üçün əlavə olaraq $2$ inək tələb olunacaq. Beləliklə, ümumi inək sayı $4 + 2 = 6$ 4 + 2 = 6 olacaq.

Alqoritmin realizasiyası

Giriş məlumatlarını oxuyuruq. Giriş sahəsinin ölçüsü $10 \times 10$ 10 \times 10-dır.

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

Tövlənin $(b_{x}, b_{y})$ (b_x, b_y), gölün $(l_{x}, l_{y})$ (l_x, l_y) və daşın $(r_{x}, r_{y})$ (r_x, r_y) koordinatlarını tapırıq.

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++

Aşağıdakı Manhettən məsafələrini hesablayırıq:

$B a r n L ak e$ BarnLake — tövlə ilə göl arasında;
$B a r n R oc k$ BarnRock — tövlə ilə daş arasında;
$L ak e R oc k$ LakeRock — göl ilə daş arasında;

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

Tövlə ilə göl arasında briqada formalaşdırmaq üçün lazım olan $r es$ inək sayını tapırıq. Bu, $(b_{x}, b_{y})$ (b_x, b_y) və $(l_{x}, l_{y})$ (l_x, l_y) nöqtələri arasındakı Manhettən məsafəsindən bir vahid azdır.

res = BarnLake - 1;

Əgər tövlə və göl eyni üfüqi və ya şaquli xəttdə yerləşirsə, daş isə onların arasındakı yolda yerləşirsə, onda zəncir qurmaq üçün lazım olan inək sayı $2$ vahid artırılmalıdır.

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

Cavabı çıxarırıq.

cout << res << endl;