Labyrinth (CSES)

Problem Link : Labyrinth

Problem Statement: You are given a map of a labyrinth, and your task is to find a path from start to end. You can walk left, right, up and down.

Input:

The first input line has two integers n and m : the height and width of the map. Then there are n lines of m characters describing the labyrinth. Each character is . (floor), # (wall), A (start), or B (end). There is exactly one A and one B in the input.

Output:

First print “YES”, if there is a path, and “NO” otherwise. If there is a path, print the length of the shortest such path and its description as a string consisting of characters L (left),  R (right),  U (up), and  D (down). You can print any valid solution.

Solution:

The given below is the input ouput for example

If you clearly observe clearly in the above example from A as a source we to need to go to B and we need 9 steps to go from A to B and as provided LDDRRRRRU is the direction

Intution:

We need to traverse from the A to B so we will be using the graph traversal algorithm and start traversing from A to B

Approach:-

I am going to use Bfs traversal from A to B , starting from A and searching for B , once B is found i will stop the traversal ,for to show the path output we need to store the parent’s of each node in a vector
if you are new to the bfs breadth first search algorithm , I suggest you to go through the following blog where i have explained it very clearly from scratch to all topics Breadth-First-Search-Part1 , you can go through all the parts

Code :

//#define KPR_111


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

int main(){
	int n,m;
	cin>>n>>m;
	vector<string> v(n);

	for(int i=0;i<n;i++)
		cin>>v[i];

	vector<vector<int>> vis(n,vector<int> (m,0));
	vector<vector<pair<int,int>>> par(n,vector<pair<int,int>> (m ));
	vector<int> dx={1,-1,0,0};
	vector<int> dy={0,0,1,-1};

	queue <pair<int,int>> q;
	pair<int,int> destination;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(v[i][j]=='A')q.push({i,j}),par[i][j]={-1,-1};
			if(v[i][j]=='B')destination={i,j};
		}
	}

	vector<pair<int,int>> path;
	while(!q.empty()){
		auto it=q.front();
		q.pop();
		int x=it.first;
		int y=it.second;

		for(int i=0;i<4;i++){
			int nrw=x+dx[i];
			int ncl=y+dy[i];
			if(nrw>=0 && nrw<n && ncl>=0 && ncl<m && (v[nrw][ncl]=='.'||v[nrw][ncl]=='B') && !vis[nrw][ncl]){
				par[nrw][ncl]={x,y};
				vis[nrw][ncl]=1;
				if(make_pair(nrw,ncl)==destination){
					break;
				}
				q.push({nrw,ncl});
			}
		}
	}

	pair<int,int> temp=destination;
	pair<int,int> parofA={-1,-1};

	if(!vis[destination.first][destination.second]){
		cout<<"NO"<<endl;
		return 0;
	}
	string s;
	while(temp!=parofA){
		pair<int,int> mk;
		
		mk=par[temp.first][temp.second];

		if(mk.first==temp.first){
			if(mk.second>temp.second)s+='L';
			else s+='R';
		}
		else if(mk.second==temp.second){
			if(mk.first>temp.first)s+='U';
			else s+='D';
		}
		temp=mk;
	}
	cout<<"YES"<<endl;
	cout<<s.size()<<endl;
	reverse(s.begin(),s.end());
	cout<<s<<endl;

}