# Chef and Telephone Network | CodeChef

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)