Zając – Omówienie zadania – II etap OIG

Zając – Omówienie zadania – II etap OIG

Szczegółowe omówienie zadania Zając:

Link do powyższego omówienia zadania Zając:
https://youtu.be/2ZL03PfmQiI?t=2302

Link do treści zadania Zając:
https://szkopul.edu.pl/problemset/problem/wQAk4d4zyJLueWkOPiNq_yD7/site


Zadanie Zając 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/2ZL03PfmQiI?t=62


Zadanie pochodzi z 2 etapu IV edycji Olimpiady Informatycznej Gimnazjalistów:
https://szkopul.edu.pl/task_archive/oig/

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 Zając, który jest omówiony w powyższym filmie i który otrzymuje 100%


#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

const int MAXN = 1000 + 7;

char polana[MAXN][MAXN];
int odl[MAXN][MAXN];
int n, m;

// skoki jakie mozemy wykonac
pair<int, int> R[8] = {
	{+1, +2},
	{+1, -2},
	{-1, +2},
	{-1, -2},
	{+2, +1},
	{+2, -1},
	{-2, +1},
	{-2, -1}
};

void BFS(pair<int, int> start) {
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j++) {
			odl[i][j] = -1;
		}
	}

	queue<pair<int, int>> Q;
	Q.push(start);
	odl[start.fi][start.se] = 0;
	while (!Q.empty()) {
		pair<int, int> v = Q.front();
		Q.pop();

		for (int k = 0; k < 8; 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 (polana[u.fi][u.se] == 'x')
				continue; 	// trafilismy na kopiec kreta

			if (odl[u.fi][u.se] == -1) { // nieodwiedzony
				odl[u.fi][u.se] = odl[v.fi][v.se] + 1;
				Q.push(u);
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);

	cin >> n >> m;
	pair<int, int> poczatek, nora;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> polana[i][j];
			if (polana[i][j] == 'z')
				poczatek = {i, j};
			if (polana[i][j] == 'n')
				nora = {i, j};
		}
	}

	BFS(poczatek);
	int d = odl[nora.fi][nora.se];
	if (d == -1)
		cout << "NIE\n";
	else
		cout << d << '\n';
	return 0;
}
Kod C++ programu Zając, który jest omówiony w powyższym filmie i który otrzymuje 100%

 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz