damu's blog

By damu, history, 5 years ago, In English

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?

  • Vote: I like it
  • +2
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

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).