# HackerEarth Bob and cities problem solution

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.

`#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("tushar\n");#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] = %lld\n",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 = %lld\n",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 = %lld\n",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("%d\n",search(pet)) ;}//printf("%d\n",ans) ;return 0 ;}`