Szczegółowe omówienie zadania Pułapka na Zygzaka ze sparingu Olimpiady Informatycznej:
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
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;
}