Oyo Hotel Guest Path Optimization
Oyo is constantly innovating its guest experience. One challenge is optimizing guest flow through our hotels, ensuring they experience the best amenities while managing resource allocation for premium services. This problem simulates a guest's journey through a multi-floor, multi-section hotel.
You are tasked with finding the maximum total amenity value a guest can accumulate when traversing from the top-left room (0,0) to the bottom-right room (M-1, N-1) of a hotel grid. Guests can only move right or down.
Each room (r, c) has a base amenity value. Some rooms are designated as "Premium Zones" and offer an additional bonus if visited. However, due to limited staff and resources for premium services, a guest can visit at most maxPremiumVisits Premium Zones throughout their entire path.
Your function should return the maximum possible total amenity value, including premium bonuses, a guest can achieve.
The function signature will be:
function maxGuestPathValue(M: number, N: number, amenityValues: number[][], isPremium: boolean[][], premiumBonuses: number[][], maxPremiumVisits: number): number
M: An integer representing the number of floors (rows) in the hotel.N: An integer representing the number of sections per floor (columns) in the hotel.amenityValues: A 2D array (M x N) where amenityValues[r][c] is the base amenity value for room (r, c).isPremium: A 2D boolean array (M x N) where isPremium[r][c] is true if room (r, c) is a Premium Zone, and false otherwise.premiumBonuses: A 2D array (M x N) where premiumBonuses[r][c] is the additional bonus value gained if room (r, c) is a Premium Zone and is visited. This value is only considered if isPremium[r][c] is true.maxPremiumVisits: An integer representing the maximum number of Premium Zones a guest is allowed to visit on their path.The function should return a single integer representing the maximum total amenity value. If no valid path exists (e.g., maxPremiumVisits is too low for a required premium start/end), return -1.
(0,0) and must reach (M-1, N-1).maxPremiumVisits constraint applies to the total number of Premium Zones visited along the entire path, not per floor or segment.maxPremiumVisits is 0, guests cannot visit any Premium Zones, even if they are on the path. The premiumBonuses for such rooms are ignored.Examples
Example 1
Input:
M = 2, N = 2, amenityValues = [[10,10],[10,10]], isPremium = [[false,true],[false,false]], premiumBonuses = [[0,50],[0,0]], maxPremiumVisits = 1
Output:
80
Note:
Path: (0,0) -> (0,1) -> (1,1). (0,0): amenity=10 (not premium) (0,1): amenity=10, premium_bonus=50 (is premium, 1 premium visit used) (1,1): amenity=10 (not premium) Total value: 10 + (10+50) + 10 = 80. This path uses 1 premium visit, which is <= maxPremiumVisits=1. This is the maximum possible value.
Example 2
Input:
M = 3, N = 3, amenityValues = [[1,1,1],[1,1,1],[1,1,1]], isPremium = [[false,true,false],[true,false,true],[false,true,false]], premiumBonuses = [[0,10,0],[10,0,10],[0,10,0]], maxPremiumVisits = 0
Output:
5
Note:
Since maxPremiumVisits is 0, no premium bonuses can be collected. All rooms contribute only their base amenity value (1 in this case). Any path from (0,0) to (2,2) consists of (3-1) + (3-1) + 1 = 5 rooms. Thus, the total value for any path is 5 * 1 = 5.
Example 3
Input:
M = 1, N = 3, amenityValues = [[10,5,20]], isPremium = [[false,true,false]], premiumBonuses = [[0,100,0]], maxPremiumVisits = 0
Output:
35
Note:
The only path is (0,0) -> (0,1) -> (0,2). (0,0): amenity=10. (0,1): amenity=5. (isPremium=true, bonus=100, but maxPremiumVisits=0, so bonus is ignored). (0,2): amenity=20. Total value: 10 + 5 + 20 = 35.
Constraints
1 <= M, N <= 10000 <= amenityValues[r][c] <= 10000 <= premiumBonuses[r][c] <= 10000 <= maxPremiumVisits <= 50amenityValues, isPremium, premiumBonuses) will have dimensions M x N.(0,0) and ending room (M-1, N-1) can be Premium Zones.Loading editor...