### damu's blog

By damu, history, 6 months ago, ,

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?

•
• +2
•

 » 6 months ago, # |   0 Auto comment: topic has been updated by damu (previous revision, new revision, compare).
 » 6 months ago, # |   0 Auto comment: topic has been updated by damu (previous revision, new revision, compare).
 » 6 months ago, # | ← Rev. 2 →   -8 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).
•  » » 6 months ago, # ^ |   0 thank you!!