Bob is living in a city in which houses are arranged in N*M blocks 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 accross left, right, up or down respectively. Bob lives in a house having coordinates (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.
Constraints
1<=N,M<=1000
1<=LCost,RCost,UCost,DCost<=10^9
1<=Q<=10^5
0<=X<=10^18
Time limit 1 second
Sample input
3 4 (N, M)
..#.
#...
..#.
1 2 3 4 (LCost, RCost,UCost, DCost)
2 3 (Stx, Sty)
3 (Q)
2 (X)
5 (X)
10 (X)
Output
3
7
9
Could anyone give hint on how to solve this problem?
My first thought was to using Dijkstra to find the shortest prices from Bob's house to all another houses. Then you store those prices in a vector, sort it, binary search with each Q to find the maximum price Y that isn't exceed X (all the number of prices behind Y + 1 = result, can easily achieve if you know Y's index).