Fire Station Response Bill
Problem statement
A city is an m x n grid. grid[i][j] is 0 for a fire station, -1 for a residence and -2 for a lake. A fire truck moves one cell up, down, left or right per step. It can drive through stations and residences but never into a lake. The distance of a residence is the fewest steps a truck needs from the nearest fire station.
The city pays for one trip to each residence a truck can reach. The tariff is percents: a residence at distance d costs baseCost * percents[d - 1] / 100, rounded down. Every distance greater than percents.length uses the last entry, percents[percents.length - 1], which works as a cap.
Return [total, unreachable]: the total cost over all reachable residences, and the number of residences no truck can reach. Unreachable residences cost nothing.
Function
fireResponseBill(grid: int[][], baseCost: int, percents: int[]) → int[]Examples
Example 1
grid = [[0,-1,-1],[-2,-2,-1],[-1,-1,-1]]baseCost = 100percents = [50,100,150]return = [750,0]The only station is at (0, 0). The lakes in row 1 force the trucks around the right edge, so the residences get distances 1, 2, 3, 4, 5 and 6 in the order (0,1), (0,2), (1,2), (2,2), (2,1), (2,0). Their costs are 50, 100 and 150, and every distance from 3 on uses the last entry, 150. The total is 50 + 100 + 150 * 4 = 750, and every residence is reachable.
Example 2
grid = [[0,-1,-1,0],[-2,-2,-2,-2],[-1,-1,-2,-1]]baseCost = 200percents = [80,100,120]return = [320,3](0,1) is one step from the left station and (0,2) is one step from the right station, so each costs 200 * 80 / 100 = 160, for 320. Row 1 is all lake, so the three residences in row 2 cannot be reached by any truck.
Example 3
grid = [[-1,-1,-1,-1,0]]baseCost = 99percents = [70,85,100,120,140]return = [370,0]The residences are 4, 3, 2 and 1 steps from the station. Their costs are 99 * 120 / 100 = 118, 99 * 100 / 100 = 99, 99 * 85 / 100 = 84 and 99 * 70 / 100 = 69, each rounded down, for a total of 370.
Constraints
m == grid.length,n == grid[i].length,1 <= m, n <= 150grid[i][j]is0,-1or-2.1 <= baseCost <= 10001 <= percents.length <= 201 <= percents[k] <= 1000