Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
  • Work with US
Programmingoneonone
Programmingoneonone

HackerEarth Bob and cities problem solution

YASH PAL, 31 July 2024
In this HackerEarth Bob and cities problem solution, Bob is living in a city in which houses are arranged in NxM block.
The city is denoted by N strings having M characters such that ‘.’ denotes house while ‘#’ denotes forests.
Bob has to pay a certain amount LCost, RCost, UCost, DCost to move 1 step across left, right, up or down respectively.
Bob lives in a house having co-ordinates (Stx , Sty) (1-Based Indexing).
You are given Q tasks contains an integer X each. In each task, you have to find number of unique houses (including his house) can be travelled using the amount X.
HackerEarth Bob and cities problem solution

HackerEarth Bob and cities problem solution.

#include<bits/stdc++.h>
using namespace std ;
#define pb push_back
#define mp make_pair
#define infile() freopen("in12.txt","r",stdin);
#define output() freopen("out12.txt","w",stdout);
#define ll long long
#define sc(t); scanf("%d",&t);
#define scl(t); scanf("%lld",&t);
#define sc2(n,m); scanf("%d%d",&n,&m);
#define scl2(n,m); scanf("%lld%lld",&n,&m);
#define debug(); printf("tusharn");
#define N 1001
#define mod 1000000007
#define printi(n) printf("%d",n);
#define inf ((1<<29)-1)
#define linf ((1LL<<60)-1)
const double eps = 1e-9;
set < ll > s ;
set < int > si ;
set < ll > :: iterator it ;
vector < ll > v ;
vector < int > vi ;

int n,m,q,k ;
int a[N][N] ;
char str[N][N] ;
ll dp[N][N] ;
int stx,sty ;
ll LL,RR,UU,DD ;
int valid(int x, int y)
{
if(x>=1&&x<=n&&y>=1&&y<=m&&a[x][y])
return 1 ;
return 0 ;
}


int search(ll x)
{
int low=0;
int high=v.size()-1;
int mid ;
int ans=0 ;
if(v.size() == 0)
return 0 ;
if(x<v[0])
return 0;
while(low<=high)
{
mid = (low+high)/2 ;
//printf("low = %d high = %d mid = %d x = %lld v[mid] = %lldn",low,high,mid,x,v[mid]) ;
if(v[mid]<=x)
{
ans=mid;
low=mid+1;
}
else
high=mid-1;
}
return ans+1;
}



void func(int xx , int yy)
{
queue < pair < int , pair < int , ll > > > q ;
q.push(mp(xx,mp(yy,0))) ;
dp[xx][yy] = 0 ;
int i,j ;
while(!q.empty())
{
int x = q.front().first ;
int y = q.front().second.first ;
ll tmp = q.front().second.second ;
//printf("x = %d y = %d tmp = %lldn",x,y,tmp) ;
q.pop() ;
int lx = x;
int ly = y-1 ;
ll cost = tmp + LL ;
if(valid(lx,ly) && cost < dp[lx][ly])
{
dp[lx][ly] = cost ;
q.push(mp(lx,mp(ly,cost))) ;
}
int rx = x;
int ry= y +1;
cost = tmp + RR ;
if(valid(rx,ry) && cost < dp[rx][ry])
{
dp[rx][ry] = cost ;
q.push(mp(rx,mp(ry,cost))) ;
}
int ux = x-1 ;
int uy = y ;
cost = tmp + UU ;
if(valid(ux,uy) && cost < dp[ux][uy])
{
dp[ux][uy] = cost ;
q.push(mp(ux,mp(uy,cost))) ;
}
int dx = x+1 ;
int dy = y ;
cost = tmp + DD ;
if(valid(dx,dy) && cost < dp[dx][dy])
{
dp[dx][dy] = cost ;
q.push(mp(dx,mp(dy,cost))) ;
}
}

for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(dp[i][j]!=linf)
v.pb(dp[i][j]) ;
}
}
sort(v.begin(),v.end());
}
int main()
{
int i , j , t ;

//infile() ;
//output() ;

sc2(n,m) ;

for(i=0;i<n;i++)
scanf("%s",str[i]) ;

scanf("%lld %lld %lld %lld",&LL,&RR,&UU,&DD );
//printf("LL = %lld RR = %lld UU = %lld DD = %lldn",LL,RR,UU,DD) ;
for(i = 1 ; i <= n ; i++ )
{
for(j=1;j<=m;j++)
{
if(str[i-1][j-1] == '.')
a[i][j] = 1 ;
else
a[i][j] = 0 ;
}
}

for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
dp[i][j]=linf ;

sc2(stx,sty) ;
func(stx,sty) ;

ll petrol ;
int ans = 0 ;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(a[i][j] == 1)
{
if(dp[i][j] <= petrol)
ans++ ;
}
}
}


//printf("sz = %d printf"("jhdsb")"n",v.size()) ;

sc(q) ;
while(q--)
{
ll pet ;
scl(pet) ;
printf("%dn",search(pet)) ;
}
//printf("%dn",ans) ;
return 0 ;
}
coding problems solutions

Post navigation

Previous post
Next post

Related website

The Computer Science

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes