Editorial for Loving Menemen
Submitting an official solution before solving the problem yourself is a bannable offence.
Türkçe
Problemi çözerken BFS(Breadth-First-Search) algoritmasını kullandık. BFS seçilen bir noktadan sırayla o noktaya olan uzaklıkları en yakın olan noktalardan en uzak olanlara doğru gezen bir algoritmadır.
Açıklama
BFS algoritmasında önce bir başlangıç noktası seçilir (sorumuz için A noktası), seçilmiş olarak işaretlenir ve bu nokta o anda boş olan Queue'ya atılır. Daha sonra Queue boşalana kadar her turda Queue'nun en önündeki değer Queue dan çıkartılır ve bu noktadan erişilebilecek ve daha önceden seçilmemiş olan noktalar seçilir. Bu noktalar Queue'ya arkadan eklenir, seçilmiş olarak işaretlenir ve O noktaya erişmek için kullandığımız nokta "ÖNCEKİ" olarak kaydedilir. Bu işlem erişilebilecek tüm noktalar gezilene kadar devam edilir ve BFS algoritması sonlanır. Daha sonra başta seçilen noktadan herhangi bir X noktasına olan yol "ÖNCEKİ" noktaları kullanılarak bulunur.
Farklılıklar
- Normal BFS ten farklı olarak bu soruda her nokta sadece bir birim yanındaki noktalara erişebilir(0-4 noktaya).
- BFS uygularken noktaların seçilmiş olup olmadığına bakmadan önce noktaların sınırlar içinde olup olmadıklarını kontrol ederek alan dışına çıkılmasının engellenmesi gerekir.
- A noktasından B noktasına ulaşmamız gerektiği için kod tüm haritayı gezmek yerine B noktasına varınca durdurulur
- B noktasına ulaşılmışsa, A noktasından B noktasına ulaşana kadar uğranan noktalar sayılarak yolun uzunluğu hesaplanır.
English
BFS(Breadth-First-Search) algorithm was used to solve this algorithm. BFS is an algorithm that travels from a selected point to every other point, starting from the closest points to the farthest points in order.
Solution
At first, the program chooses a starting point, marks it as visited(chosen in the solution below), and adds it to the empty Queue. After that, in every turn, the point at the front of the Queue gets ejected from the Queue, assigned as the current point, and points that are adjacent to this point that hasn't been visited before will be selected until the Queue is empty. These points would be pushed to the Queue from the back, marked as visited, and the current point would be assigned as its "PREVIOUS"(prev in the solution below) point. This process would normally continue until every point within reach has been visited. Then the path from the initially selected point to any arbitrary X point would be found using the "PREVIOUS" points.
Differences
- Since this problem uses a map approach, every point can only access points that are adjacent to it(0-4 points).
- When applying BFS, before checking whether the points are selected or not, it is necessary to check whether the points are within the boundaries to avoid going out of the area.
- Since we need to get from point A to point B, the code is stopped when we reach point B instead of traveling the whole map.
- If point B has been reached, the length of the road would be calculated by counting the points visited from point A to point B (Using "PREVIOUS" variables).
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m;
struct point{
char c;
bool chosen=false;
pair<int,int> prev;
void previous(pair<int,int> p){
chosen=true;
prev=p;
}
//ENGLISH: the previous function sets the current point as chosen and sets our previous location on the map
//TURKISH: previous fonksiyonu hem şu anki noktayı seçilmiş olarak işaretler hem de bir önceki noktayı kaydeder
};
int main(){
cin>>n>>m;
point arr[n][m];
pair<int,int> A,B,current,next;
for(int i=0;i<n;i++)for(int j=0;j<m;j++){
cin>>arr[i][j].c;
if(arr[i][j].c=='#')arr[i][j].chosen=true;
//ENGLISH: Marking the walls as chosen so that we can skip them while creating our path
//TURKISH: Duvarları BFS'i uygularken es geçebilmek için chosen olarak işaretliyoruz.
if(arr[i][j].c=='A')A=make_pair(i,j);
else if(arr[i][j].c=='B')B=make_pair(i,j);
}
queue<pair<int,int>> Q;
arr[A.first][A.second].chosen=true;
arr[A.first][A.second].prev=make_pair(-1,-1);
arr[B.first][B.second].prev=make_pair(-1,-1);
Q.push(A);
bool flag=false;
pair<int,int> VECTORS[4]{make_pair(0,-1),make_pair(-1,0),make_pair(0,1),make_pair(1,0)};
while(!Q.empty()){
current=Q.front();
Q.pop();
for(int i=0;i<4;i++){
next=make_pair(current.first+VECTORS[i].first,current.second+VECTORS[i].second);
if(next.first>0&&next.first<n&&!arr[next.first][next.second].chosen){
if(arr[next.first][next.second].c=='B'){ //B FOUND
flag=true;
arr[next.first][next.second].previous(current);
break;
}
else if(arr[next.first][next.second].c=='.'){
arr[next.first][next.second].previous(current);
Q.push(next);
}
}
/* ENGLISH: This "for loop" checks points adjacent to our current point and puts the
* unchosen valid points to BFS Queue. These points are:
* (X-1,Y),(X,Y-1),(X+1,Y),(X,Y+1)
*
* TURKISH: Bu "for döngüsü" mevcut noktanın yanındaki noktalardan geçerli ve seçilmemiş
* olanları BFS queuemuza koyuyor. Bu noktalar:
* (X-1,Y), (X,Y-1), (X+1,Y), (X,Y+1)
*/
}
if(flag)break;
}
if(arr[B.first][B.second].prev.first==-1){
//ENGLISH: If B is not accessible its prev variable wouldn't have changed after the BFS loop has ended.
//TURKISH: Eğer B, A tarafından erişilemezse prev değişkeni döngü içinde değişmemiştir
cout<<-1<<endl;
return 0;
}
current=B;
int count=0;
while(current!=A){
count++;
current=arr[current.first][current.second].prev;
}
//ENGLISH: If B is accessable from A then we can easily count the points while going back, until we find A.
//TURKISH: Eğer B, A tarafından erişilebilirse nokta nokta geri giderek kaç hamlede B ye erişildiğini bulabiliriz.
cout<<count<<endl;
}