CHFTN : Editorial
Author : divyesh196
Tester : divyesh196
Editorial : divyesh196
Difficulty :- Medium
Prereqisites :- BFS
Solution
Use BFS , as start from pushing the source vertex in queue, and move to all next
possible level ( if possible ) from current state and update distance of next level as cur_dist+1, if queue becomes empty and we does not reach destination print -1, otherwise print distance from source vertex to destination vertex.
#include<bits/stdc++.h>
#define ll long long
#define mk make_pair
#define pb push_back
#define pp pair<ll,ll>
using namespace std;
typedef pair<ll,ll>p;
ll i,j;
char a[100][100];
ll dx[]={1,-1,0,0};
ll dy[]={0,0,1,-1};
struct cell
{
ll x,y,z;
};
ll issafe(ll x, ll y, ll n, ll m)
{
if(x>=0 && y>=0 && x<n && x<m && y<n && y<m && a[x][y]!='x')
return 1;
else
return 0;
}
ll solve(ll n, ll m, ll x1, ll y1, ll x2, ll y2)
{
bool vis[n+1][m+1];
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
vis[i][j]=false;
}
}
queue<cell>q;
set<p>s;
s.insert(mk(x1,y1));
q.push({x1,y1,0});
cell t;
vis[x1][y1]=true;
while(!q.empty())
{
t=q.front();
q.pop();
if(a[t.x][t.y]=='D')
return t.z;
for(i=0;i<4;i++)
{
ll xx=t.x+dx[i];
ll yy=t.y+dy[i];
p k=mk(xx,yy);
if(issafe(xx,yy,n,m) && s.find(k)==s.end() && a[xx][yy]!='x')
{
s.insert(mk(xx,yy));
vis[xx][yy]=true;
if(a[xx][yy]!='x')
q.push({xx,yy,t.z+1});
}
}
}
return -1;
}
int main()
{
ll n,m;
cin>>n>>m;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
cin>>a[i][j];
ll x1,y1,x2,y2;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(a[i][j]=='S')
{
x1=i;
y1=j;
}
if(a[i][j]=='D')
{
x2=i;
y2=j;
}
}
}
cout<<solve(n,m,x1,y1,x2,y2)<<endl;
}
// Time Complexity :- O(V+E)