HackerEarth Jungle Run problem solution

In this HackerEarth Jungle Run problem solution You are lost in a dense jungle and it is getting dark. There is at least one path that leads you to the city on the other side but you cannot see anything until you are right in front of it as the trees and bushes obscure the path.

Devise an algorithm that is guaranteed to find the way out. Your goal is to go out of the jungle as fast as you can before it gets dark.

HackerEarth Jungle Run problem solution.

#include<bits/stdc++.h>
#define fori(z,n) for(int i=z;i<n;i++)
#define forj(z,n) for(int j=z;j<n;j++)
#define fork(z,n) for(int k=z;k<n;k++)

using namespace std;

char str[1005][1005];
bool visited[1000005];
int x[]={1,-1,0,0};
int y[]={0,0,-1,1};
int dist[1000005];
vector<int> v[1000005];
int main()
{
 //freopen("input.in", "r", stdin);
 int strt,end,n;
 cin>>n;
 fori(0,n)
 {

  forj(0,n) {
        cin>>str[i][j];
        if(str[i][j]=='S')
        {


          strt=i*n+j;
          str[i][j]='P';
        }
        if(str[i][j]=='E')
        {


            end=i*n+j;
            str[i][j]='P';
        }

  }
 }

 fori(0,n)
 {

     forj(0,n)
     {
         if(str[i][j]=='P')
         {
             if(i+1<n && str[i+1][j]=='P')
             {
             v[(i*n+j)].push_back((i+1)*n+j);
             v[((i+1)*n+j)].push_back((i)*n+j);
             }
               if(j+1<n && str[i][j+1]=='P')
             {
             v[(i*n+j)].push_back((i)*n+j+1);
             v[((i)*n+j+1)].push_back((i)*n+j);
             }
         }
     }
 }

 queue<int> q;
 for(int i=0;i<n*n;i++)
 {

    dist[i]=-1;
    visited[i]=false;
 }
 q.push(strt);
 dist[strt]=0;
 while(!q.empty())
 {
     int k=q.front();
     q.pop();
     if(!visited[k])
     {
         visited[k]=true;
         for(int i:v[k])
         {
           if(!visited[i])
           {
            q.push(i);
            if(dist[i]==-1)
                dist[i]=dist[k]+1;

           }
         }
     }
 }
 cout<<dist[end];
}

HackerEarth Jungle Run problem solution.

Leave a Reply