Omówienie zadania Pułapka na Zygzaka / Olimpiada Informatyczna Juniorów

Omówienie zadania Pułapka na Zygzaka / Olimpiada Informatyczna Juniorów

Szczegółowe omówienie zadania Pułapka na Zygzaka ze sparingu Olimpiady Informatycznej:
https://youtu.be/f0elTQkIyN0?t=5442

Link do zadania Pułapka na Zygzaka:
Link do contestu stałego gdzie można wrzucać rozwiązania zadania Pułapka na Zygzaka:


Zadanie Pułapka na Zygzaka to ciekawe zadanie grafowe które zbliża nas do realnych problemów gdzie mamy grafy dynamiczne – ze zmieniającymi się wierzchołkami i  krawędziami.

Okazuje się, że te problemy są proste.
Zadanie ćwiczy algorytm BFS który pozwala znaleźć najkrótszą drogę w grafie o krawędziach które nie mają wag.
Zadanie Pułapka na Zygzaka pochodzi ze sparingu Olimpiady Informatycznej Juniorów.
Każdy kto chce uzyskać dobry wynik w Olimpiadzie Informatycznej Juniorów lub Olimpiadzie Informatycznej Licealistów ma wielką szansę by zaatakować to zadanie!
Jak się uczyć na podstawie takiego zadania?
https://tiny.pl/7x1gg
——-
Kod C++ programu Pułapka na Zygzaka, który jest omówiony w powyższym filmie i który otrzymuje 100%

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

const int N=2030;
int Plansza[N][N];
int OdlegloscW[N][N];
int OdlegloscB[N][N];
int RozaX[5]={0, 0, 1, 0, -1};
int RozaY[5]={0, 1, 0, -1, 0};
queue< pair<int, int> > Kolejka;

void LiczOdlegloscW(int n, int m, int V){
	pair<int, int> aktu;
	while( !Kolejka.empty() ){
		aktu=Kolejka.front();
		Kolejka.pop();
		for(int i=1; i<=4; i++){
			if( OdlegloscW[aktu.first+RozaX[i]][aktu.second+RozaY[i]]==-1 && Plansza[aktu.first+RozaX[i]][aktu.second+RozaY[i]]==0 ){
				OdlegloscW[aktu.first+RozaX[i]][aktu.second+RozaY[i]]=OdlegloscW[aktu.first][aktu.second]+V;
				Kolejka.push( {aktu.first+RozaX[i], aktu.second+RozaY[i]} );
			}
		}
	}
}

int xk = -1, yk = -1;

void LiczOdlegloscB(int n, int m){
	pair<int, int> aktu;
	Kolejka.push( {xk, yk} );
	OdlegloscB[xk][yk]=0;
	while( !Kolejka.empty() ){
		aktu=Kolejka.front();
		Kolejka.pop();
		for(int i=1; i<=4; i++){
			if( OdlegloscB[aktu.first+RozaX[i]][aktu.second+RozaY[i]]==-1 && Plansza[aktu.first+RozaX[i]][aktu.second+RozaY[i]]==0 && OdlegloscB[aktu.first][aktu.second]+1<OdlegloscW[aktu.first+RozaX[i]][aktu.second+RozaY[i]]){
				OdlegloscB[aktu.first+RozaX[i]][aktu.second+RozaY[i]]=OdlegloscB[aktu.first][aktu.second]+1;
				Kolejka.push( {aktu.first+RozaX[i], aktu.second+RozaY[i]} );
			}
		}
	}
}

int main (){
	int n, m, V;
	char znak;
	cin>>n>>m>>V;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			cin>>znak;
			if(znak=='#') Plansza[i][j]=1;
			if(znak=='.') Plansza[i][j]=0;
			if(znak=='*') Plansza[i][j]=2;
			if(znak=='Z') { xk = i; yk = j; }
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			OdlegloscW[i][j]=OdlegloscB[i][j]=-1;

			if(Plansza[i][j]==2){
				Kolejka.push( {i, j} );
				OdlegloscW[i][j]=0;
			}
		}
	}
	LiczOdlegloscW(n, m, V);
	LiczOdlegloscB(n, m);
	cout << OdlegloscB[1][1] << "\n";
	return 0;
}
Link do pliku z kodem C++ zadania Pułapka na Zygzaka 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz