795. How Far the Tour Gets
A museum is a grid of R rows and C columns; room (r, c) charges fee[r][c] to enter.
A visitor starts outside the top left room and may enter a room only when the fee is STRICTLY
below the money they carry. From a room they may move to a room sharing a side, again paying only
if the fee is strictly below their money. Fees are not deducted, the same note is shown at every
door.
For each of q visitors, print how many rooms that visitor can see in total, counting the top
left room when they manage to get in at all.
1 2 3
2 5 7 budgets 5, 6, 2 -> 5, 8, 1
3 5 1
With 5 in hand the visitor enters the top left room and reaches the rooms charging 1, 2, 3, 2 and 3, which is 5 rooms; the 5s and the 7 are all shut. With 2 in hand only the room charging 1 is open, so the answer is 1.
## Why one search per visitor is too slow
A single visitor is a breadth first search over the rooms strictly cheaper than their budget,
O(R * C). With 10^5 visitors on a 300 * 300 museum that is 9 * 10^9 room visits.
## The monotone structure
A richer visitor sees a superset of what a poorer one sees. Every room reachable on a budget of
x is reachable on any budget above x, by the very same route. So the counts, read in
increasing order of budget, never fall.
That is the same monotone property binary search exploits, used a different way: rather than halving a range to answer one question, the visitors are sorted and the region is GROWN once, never rebuilt.
## The sweep
Keep a frontier of rooms that have been touched but not yet paid for, in a min-heap keyed by fee, seeded with the top left room. Then, for each budget in increasing order:
while the cheapest room on the frontier costs strictly less than the budget:
take it, add 1 to the running count, and push its four neighbours
answer for this visitor = the running count
Every room enters the heap at most once and leaves at most once, so the whole sweep is
O(R * C * log(R * C) + q log q) however many visitors there are.
## The boundary that breaks a careless implementation
The start room is not free. If fee[0][0] is not strictly below the budget the answer is 0, not
1, and a sweep that seeds the count at 1 instead of seeding the HEAP gets every poor visitor
wrong. Pushing the start room onto the heap and letting the same rule apply to it is what makes
the single case work.
The second is the strictness: a budget equal to a fee does not open that door. Two of the tests sit exactly on that line.
## Width
Fees reach 10^9 and a budget may be 10^9 + 1, both inside a signed 32-bit integer. The
running count is at most R * C, which is 9 * 10^4, so it fits too, and nothing in this
problem overflows.
## Related problems
Problem 794 sorts its questions and sweeps a union-find for the same reason. Problem 791 searches a single grid threshold instead of answering many.
## Cost
Time O(R * C * log(R * C) + q log q). Space O(R * C + q).
Constraints - `1 ≤ R ≤ 300` - `1 ≤ C ≤ 300` - `1 ≤ q ≤ 100000` - `1 ≤ fee[r][c] ≤ 10^9` - `1 ≤ budget ≤ 10^9 + 1`
Input
The first line contains three integers R, C and q.
Each of the next R lines contains C integers, the fees of one row in order.
The last line contains q integers, the budgets of the visitors in the order asked.
Output
Print q lines. Line j holds one integer, the number of rooms the jth visitor can see, counting the top left room when it is open to them.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.