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 ;
}