Zadanie 1: BRYGADA WIADROWA

Link do oryginalnego zadania:
http://www.usaco.org/index.php?page=viewproblem2&cpid=939

https://youtu.be/xZCGtGh2he0?t=1443

Na farmie wybuchł pożar, a krowy się śpieszą, żeby spróbować go ugasić!
Farma ma postać siatki 10 x 10, na przykład:
……….
……….
……….
..B…….
……….
…..R….
……….
……….
…..L….
……….

Znak ‘B’ oznacza stodołę, która właśnie zapłonęła. Znak ‘L’ symbolizuje jezioro, a ‘R’ przedstawia pozycję wielkiego kamienia.

Krowy chcą utworzyć ‘brygadę wiadrową’ ustawiając się po drodze pomiędzy jeziorem a stodołą, żeby mogły podawać sobie wiadra z wodą wzdłuż drogi by pomóc ugasić pożar. Wiadro może przejść od krowy do krowy, jeśli druga krowa styka się z pierwszą z lewej, prawej, dołu lub góry. To samo dla krowy przy jeziorze — krowa może tylko napełnić wiadro z jeziora, jeśli styka się z jeziorem. Podobnie, tylko krowa stykająca się ze stodołą może wylać na nią wiadro.

Ustal minimalną liczbę pól oznaczonych ‘.’, które powinny zostać zajęte przez krowy, aby utworzyć działającą brygadę wiadrową.

Krowa nie może zostać postawiona na dużym kamieniu. Możesz przyjąć, że stodoła i jezioro nigdy nie będą się ze sobą stykać.

FORMAT WCZYTANIA(plik buckets.in):
Plik wczytywany zawiera 10 rzędów po 10 znaków, opisujących układ farmy.

FORMAT WYJŚCIA(plik buckets.out):
Wypisz jedną liczbę całkowitą, będącą minimalną liczbą krów potrzebną do utworzenia skutecznej brygady wiadrowej.

PRZYKŁAD WEJŚCIA:
……….
……….
……….
..B…….
……….
…..R….
……….
……….
…..L….
……….

WYJŚCIE:
7

W tym przykładzie, jest m. in taka możliwość, która zawiera optymalny układ krów(7):
……….
……….
……….
..B…….
..C…….
..CC.R….
…CCC….
…..C….
…..L….
……….

—
Autorem tłumaczenia jest Erwin Trynkus z XIV Liceum im. Stanisława Staszica

 

---

-
#include <bits/stdc++.h>
using namespace std;

int main(){
freopen("buckets.in", "r", stdin);
freopen("buckets.out", "w", stdout);

 char field;
 int x, y;
 int barn_x, barn_y;
 int rock_x, rock_y;
 int lake_x, lake_y;

 for (y=1; y<=10; ++y) {
    for (x=1; x<=10; ++x) { cin >> field;
       if (field == 'B') {
          barn_x = x;
		  barn_y = y;
	   }
       if (field == 'R') {
          rock_x = x;
          rock_y = y;
       }
       if (field == 'L') {
          lake_x = x;
	  lake_y = y;
       }
    }
 }
 
 if ( barn_x == lake_x ) {
 	if ( (rock_x==barn_x) && (abs(lake_y-barn_y)>abs(rock_y-barn_y)) ) {
 	   cout << abs(lake_y-barn_y) + 1;
	   return 0;		 		
	 } else {
 	   cout << abs(lake_y-barn_y) - 1; return 0; } } if ( barn_y == lake_y ) { if ( (rock_y==barn_y) && (abs(lake_x-barn_x)>abs(rock_x-barn_x)) ) {
 	   cout << abs(lake_x-barn_x) + 1;
	   return 0;		 		
	 } else {
 	   cout << abs(lake_x-barn_x) - 1;
	   return 0;		
	}	
 }
 cout << abs(lake_y-barn_y) + abs(lake_x-barn_x) - 1 << "\n";

 return 0;
}

———————-
Radości z rozwiązanych zadań!