Sklep – Omówienie zadania

Sklep – Omówienie zadania

Szczegółowe omówienie zadania Sklep:

Link do powyższego omówienia zadania Sklep:
https://youtu.be/v3dLlr0yFkc?t=1652

Link do treści zadania Sklep oraz możliwości umieszczania rozwiązań:
https://ki.staszic.waw.pl/task.php?name=sklep


Zadanie Sklep 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


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 Sklep, 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;
typedef long long ll;

const int MAXN = 1000*1000 + 7;

vector<char> sklep[MAXN];
vector<int> odl[MAXN];
int n, m;

// ruchy jakie mozemy wykonac
pair<int, int> R[4] = {
	{-1,  0},	// gora
	{ 0, -1}, 	// lewo
	{ 0, +1}, 	// prawo
	{+1,  0}  	// dol
};

void BFS(pair<int, int> start)
{
	for (int i = 0; i < n; i++)
		odl[i].resize(m, -1); // rozszerz wektor do rozmiaru m i wypelnij -1

	queue<pair<int, int>> Q; // do rozpatrzenia
	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 < 4; k++) {
			pair<int, int> u;
			u.fi = v.fi + R[k].fi;
			u.se = v.se + R[k].se;

			if ((u.fi < 0) || (u.fi >= n) || (u.se < 0) || (u.se >= m))
				continue;  	// jestesmy poza plansza
			if (sklep[u.fi][u.se] == 'R')
				continue;	// regal

			if (odl[u.fi][u.se] == -1) { // wierzcholek u 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> wejscie, trampki;
	for (int i = 0; i < n; i++) {
		sklep[i].resize(m); // rozszerz wektor do rozmiaru m
		for (int j = 0; j < m; j++) {
			cin >> sklep[i][j];
			if (sklep[i][j] == 'W')
				wejscie = {i, j};
			if (sklep[i][j] == 'T')
				trampki = {i, j};
		}
	}

	BFS(wejscie);

	cout << odl[trampki.fi][trampki.se] << '\n';
	return 0;
}
Kod C++ programu Sklep, który jest omówiony w powyższym filmie i który otrzymuje 100%

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz