Szczegółowe omówienie zadania Cow Beauty Pageant:

Link do powyższego omówienia zadania Cow Beauty Pageant:
https://youtu.be/v3dLlr0yFkc?t=3314

Link do treści zadania Cow Beauty Pageant oraz możliwości umieszczania rozwiazań:
https://szkopul.edu.pl/problemset/problem/cbp/site

Link do oryginalnej treści zadania Cow Beauty Pageant:
http://www.usaco.org/index.php?page=viewproblem2&cpid=88

–
Zadanie Cow Beauty Pageant jest zadaniem pokazującym działanie algorytmu BFS:
https://youtu.be/2ZL03PfmQiI?t=2965
Symulacja BFS:
https://youtu.be/2ZL03PfmQiI?t=3690
Kod BFS:
https://youtu.be/2ZL03PfmQiI?t=5074
Dlaczego algorytm BFS jest ważny?
https://youtu.be/v3dLlr0yFkc?t=27

–
Zadanie Cow Beauty Pageant pochodzi z Amerykańskiej Olimpiady Informatycznej USACO, poziom Silver – odpowiednik etapu 1 – 2 Olimpiady Informatycznej Juniorów.

Zadanie Omawia Tomek Kwiatkowski – finalista Olimpiady Informatycznej:
https://youtu.be/2ZL03PfmQiI?t=2175

–
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz:
https://youtu.be/pkLXuuOe_qA?t=3625

–
Kod C++ programu Cow Beauty Pageant, który jest omówiony w powyższym filmie i który otrzymuje 100%

–

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MAXN = 50 + 7;
const int INF = 1000*1000*1000 + 7;
char pattern[MAXN][MAXN];
bool odw[MAXN][MAXN];
int nr[MAXN][MAXN];
int odl[4][MAXN][MAXN];
int najblizej[4][4];
vector<pair<int, int>> akt_wierzcholki; // do BFS_odl()
// mozliwe ruchy
pair<int, int> R[4] = {
{-1, 0}, 	// gora
{0, +1}, 	// prawo
{+1, 0},	// dol
{0, -1}		// lewo
};
int n, m;
void BFS_nr(pair<int, int> start, int akt_nr)
{
queue<pair<int, int>> Q;
Q.push(start);
odw[start.fi][start.se] = true;
while (!Q.empty()) {
pair<int, int> v = Q.front();
Q.pop();
// zaznaczamy numer spojnej
nr[v.fi][v.se] = akt_nr;
for (int k = 0; k < 4; k++) {
pair<int, int> u;
u.fi = v.fi + R[k].fi;
u.se = v.se + R[k].se;
if ((u.fi < 1) || (u.fi > n) || (u.se < 1) || (u.se > m)) 
continue; 	// jestesmy poza plansza
if (pattern[u.fi][u.se] == '.')
continue;	// . nas nie interesuje - chodzimy tylko po X
if (!odw[u.fi][u.se]) { // jezeli nieodwiedzony
odw[u.fi][u.se] = true;
Q.push(u);
}
}
}
}
void BFS_odl(int akt_nr)
{
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
odl[akt_nr][i][j] = -1;
}
}
queue<pair<int, int>> Q;
// zaczynamy z kilku wierzcholkow naraz
for (int i = 0; i < akt_wierzcholki.size(); i++) {
pair<int, int> v = akt_wierzcholki[i];
Q.push(v);
odl[akt_nr][v.fi][v.se] = 0;
}
while (!Q.empty()) {
pair<int, int> v = Q.front();
Q.pop();
for (int k = 0; k < 4; k++) {
pair<int, int> u;
u.fi = v.fi + R[k].fi;
u.se = v.se + R[k].se;
if ((u.fi < 1) || (u.fi > n) || (u.se < 1) || (u.se > m)) 
continue; 	// jestesmy poza plansza
if (odl[akt_nr][u.fi][u.se] == -1) { // jezeli nieodwiedzony
int odl_u = odl[akt_nr][v.fi][v.se] + 1;
odl[akt_nr][u.fi][u.se] = odl_u;
// jesli trafilismy na spojna - uzupelniamy odleglosci miedzy nimi
if (nr[u.fi][u.se] != 0) {
int nr_u = nr[u.fi][u.se];
najblizej[akt_nr][nr_u] = min(odl_u - 1, najblizej[akt_nr][nr_u]);
}
Q.push(u);
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> pattern[i][j];
}
}
// zaznaczamy spojne fragmenty X-ów
int akt_nr = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// jesli trafilismy na nieodwiedzony X - to jest to kolejna spojna
if (pattern[i][j] == 'X' && !odw[i][j]) {
BFS_nr({i, j}, akt_nr);
akt_nr++;
}
}
}
for (int i1 = 1; i1 <= 3; i1++) {
for (int i2 = 1; i2 <= 3; i2++) {
najblizej[i1][i2] = INF;
}
}
// obliczamy odleglosci od kazdej spojnej 
for (int akt_nr = 1; akt_nr <= 3; akt_nr++) {
// znajdujemy wierzcholki o numerze akt_nr
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (nr[i][j] == akt_nr)
akt_wierzcholki.pb({i, j});
}
}
BFS_odl(akt_nr);
akt_wierzcholki.clear();
}
int wyn = INF;
// opcje 1-3. (laczymy (1-2, 2-3) lub (2-3, 3-1) lub (3-1, 1-2))
wyn = min(najblizej[1][2] + najblizej[2][3], wyn);
wyn = min(najblizej[2][3] + najblizej[3][1], wyn);
wyn = min(najblizej[3][1] + najblizej[1][2], wyn);
// opcja 4. ('spotkanie' w jakims jednym wierzcholku)
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (pattern[i][j] == '.') {
int odl_laczna = (odl[1][i][j] - 1)
+ (odl[2][i][j] - 1)
+ (odl[3][i][j] - 1) + 1;
wyn = min(odl_laczna, wyn);
}
}
}
cout << wyn << '\n';
return 0;
}