2146. K Highest Ranked Items Within a Price Range Medium

1/**
2 * [2146] K Highest Ranked Items Within a Price Range
3 *
4 * You are given a 0-indexed 2D integer array grid of size m x n that represents a map of the items in a shop. The integers in the grid represent the following:
5 * 
6 * 	0 represents a wall that you cannot pass through.
7 * 	1 represents an empty cell that you can freely move to and from.
8 * 	All other positive integers represent the price of an item in that cell. You may also freely move to and from these item cells.
9 * 
10 * It takes 1 step to travel between adjacent grid cells.
11 * You are also given integer arrays pricing and start where pricing = [low, high] and start = [row, col] indicates that you start at the position (row, col) and are interested only in items with a price in the range of [low, high] (inclusive). You are further given an integer k.
12 * You are interested in the positions of the k highest-ranked items whose prices are within the given price range. The rank is determined by the first of these criteria that is different:
13 * <ol>
14 * 	Distance, defined as the length of the shortest path from the start (shorter distance has a higher rank).
15 * 	Price (lower price has a higher rank, but it must be in the price range).
16 * 	The row number (smaller row number has a higher rank).
17 * 	The column number (smaller column number has a higher rank).
18 * </ol>
19 * Return the k highest-ranked items within the price range sorted by their rank (highest to lowest). If there are fewer than k reachable items within the price range, return all of them.
20 *  
21 * Example 1:
22 * <img alt="" src="https://assets.leetcode.com/uploads/2021/12/16/example1drawio.png" style="width: 200px; height: 151px;" />
23 * Input: grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]], pricing = [2,5], start = [0,0], k = 3
24 * Output: [[0,1],[1,1],[2,1]]
25 * Explanation: You start at (0,0).
26 * With a price range of [2,5], we can take items from (0,1), (1,1), (2,1) and (2,2).
27 * The ranks of these items are:
28 * - (0,1) with distance 1
29 * - (1,1) with distance 2
30 * - (2,1) with distance 3
31 * - (2,2) with distance 4
32 * Thus, the 3 highest ranked items in the price range are (0,1), (1,1), and (2,1).
33 * 
34 * Example 2:
35 * <img alt="" src="https://assets.leetcode.com/uploads/2021/12/16/example2drawio1.png" style="width: 200px; height: 151px;" />
36 * Input: grid = [[1,2,0,1],[1,3,3,1],[0,2,5,1]], pricing = [2,3], start = [2,3], k = 2
37 * Output: [[2,1],[1,2]]
38 * Explanation: You start at (2,3).
39 * With a price range of [2,3], we can take items from (0,1), (1,1), (1,2) and (2,1).
40 * The ranks of these items are:
41 * - (2,1) with distance 2, price 2
42 * - (1,2) with distance 2, price 3
43 * - (1,1) with distance 3
44 * - (0,1) with distance 4
45 * Thus, the 2 highest ranked items in the price range are (2,1) and (1,2).
46 * 
47 * Example 3:
48 * <img alt="" src="https://assets.leetcode.com/uploads/2021/12/30/example3.png" style="width: 149px; height: 150px;" />
49 * Input: grid = [[1,1,1],[0,0,1],[2,3,4]], pricing = [2,3], start = [0,0], k = 3
50 * Output: [[2,1],[2,0]]
51 * Explanation: You start at (0,0).
52 * With a price range of [2,3], we can take items from (2,0) and (2,1). 
53 * The ranks of these items are: 
54 * - (2,1) with distance 5
55 * - (2,0) with distance 6
56 * Thus, the 2 highest ranked items in the price range are (2,1) and (2,0). 
57 * Note that k = 3 but there are only 2 reachable items within the price range.
58 * 
59 *  
60 * Constraints:
61 * 
62 * 	m == grid.length
63 * 	n == grid[i].length
64 * 	1 <= m, n <= 10^5
65 * 	1 <= m * n <= 10^5
66 * 	0 <= grid[i][j] <= 10^5
67 * 	pricing.length == 2
68 * 	2 <= low <= high <= 10^5
69 * 	start.length == 2
70 * 	0 <= row <= m - 1
71 * 	0 <= col <= n - 1
72 * 	grid[row][col] > 0
73 * 	1 <= k <= m * n
74 * 
75 */
76pub struct Solution {}
77
78// problem: https://leetcode.com/problems/k-highest-ranked-items-within-a-price-range/
79// discuss: https://leetcode.com/problems/k-highest-ranked-items-within-a-price-range/discuss/?currentPage=1&orderBy=most_votes&query=
80
81// submission codes start here
82
83impl Solution {
84    pub fn highest_ranked_k_items(grid: Vec<Vec<i32>>, pricing: Vec<i32>, start: Vec<i32>, k: i32) -> Vec<Vec<i32>> {
85        vec![]
86    }
87}
88
89// submission codes end
90
91#[cfg(test)]
92mod tests {
93    use super::*;
94
95    #[test]
96    fn test_2146() {
97    }
98}
99