Cow Beauty Pageant – Omówienie zadania z Amerykańskiej Olimpiady Informatycznej USACO

Cow Beauty Pageant – Omówienie zadania z Amerykańskiej Olimpiady Informatycznej USACO

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.

Daje piękny wpis do CV:
https://youtu.be/P2sLFZBjOmM?t=7223

Dlaczego warto brać udział w Amerykańskiej Olimpiady Informatycznej USACO?
https://youtu.be/K7fZfJ8nN6A?t=6848

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;
}
Kod C++ programu Cow Beauty Pageant, który jest omówiony w powyższym filmie i który otrzymuje 100%

 

 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz