<p>You are given a <strong>0-indexed</strong> 2D integer array <code>grid</code> of size <code>m x n</code> that represents a map of the items in a shop. The integers in the grid represent the following:</p>

<ul>
	<li><code>0</code> represents a wall that you cannot pass through.</li>
	<li><code>1</code> represents an empty cell that you can freely move to and from.</li>
	<li>All other positive integers represent the price of an item in that cell. You may also freely move to and from these item cells.</li>
</ul>

<p>It takes <code>1</code> step to travel between adjacent grid cells.</p>

<p>You are also given integer arrays <code>pricing</code> and <code>start</code> where <code>pricing = [low, high]</code> and <code>start = [row, col]</code> indicates that you start at the position <code>(row, col)</code> and are interested only in items with a price in the range of <code>[low, high]</code> (<strong>inclusive</strong>). You are further given an integer <code>k</code>.</p>

<p>You are interested in the <strong>positions</strong> of the <code>k</code> <strong>highest-ranked</strong> items whose prices are <strong>within</strong> the given price range. The rank is determined by the <strong>first</strong> of these criteria that is different:</p>

<ol>
	<li>Distance, defined as the length of the shortest path from the <code>start</code> (<strong>shorter</strong> distance has a higher rank).</li>
	<li>Price (<strong>lower</strong> price has a higher rank, but it must be <strong>in the price range</strong>).</li>
	<li>The row number (<strong>smaller</strong> row number has a higher rank).</li>
	<li>The column number (<strong>smaller</strong> column number has a higher rank).</li>
</ol>

<p>Return <em>the </em><code>k</code><em> highest-ranked items within the price range <strong>sorted</strong> by their rank (highest to lowest)</em>. If there are fewer than <code>k</code> reachable items within the price range, return <em><strong>all</strong> of them</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/16/example1drawio.png" style="width: 200px; height: 151px;" />
<pre>
<strong>Input:</strong> grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]], pricing = [2,5], start = [0,0], k = 3
<strong>Output:</strong> [[0,1],[1,1],[2,1]]
<strong>Explanation:</strong> You start at (0,0).
With a price range of [2,5], we can take items from (0,1), (1,1), (2,1) and (2,2).
The ranks of these items are:
- (0,1) with distance 1
- (1,1) with distance 2
- (2,1) with distance 3
- (2,2) with distance 4
Thus, the 3 highest ranked items in the price range are (0,1), (1,1), and (2,1).
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/16/example2drawio1.png" style="width: 200px; height: 151px;" />
<pre>
<strong>Input:</strong> grid = [[1,2,0,1],[1,3,3,1],[0,2,5,1]], pricing = [2,3], start = [2,3], k = 2
<strong>Output:</strong> [[2,1],[1,2]]
<strong>Explanation:</strong> You start at (2,3).
With a price range of [2,3], we can take items from (0,1), (1,1), (1,2) and (2,1).
The ranks of these items are:
- (2,1) with distance 2, price 2
- (1,2) with distance 2, price 3
- (1,1) with distance 3
- (0,1) with distance 4
Thus, the 2 highest ranked items in the price range are (2,1) and (1,2).
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/30/example3.png" style="width: 149px; height: 150px;" />
<pre>
<strong>Input:</strong> grid = [[1,1,1],[0,0,1],[2,3,4]], pricing = [2,3], start = [0,0], k = 3
<strong>Output:</strong> [[2,1],[2,0]]
<strong>Explanation:</strong> You start at (0,0).
With a price range of [2,3], we can take items from (2,0) and (2,1). 
The ranks of these items are: 
- (2,1) with distance 5
- (2,0) with distance 6
Thus, the 2 highest ranked items in the price range are (2,1) and (2,0). 
Note that k = 3 but there are only 2 reachable items within the price range.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= m * n &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= grid[i][j] &lt;= 10<sup>5</sup></code></li>
	<li><code>pricing.length == 2</code></li>
	<li><code>2 &lt;= low &lt;= high &lt;= 10<sup>5</sup></code></li>
	<li><code>start.length == 2</code></li>
	<li><code>0 &lt;= row &lt;= m - 1</code></li>
	<li><code>0 &lt;= col &lt;= n - 1</code></li>
	<li><code>grid[row][col] &gt; 0</code></li>
	<li><code>1 &lt;= k &lt;= m * n</code></li>
</ul>

class Solution:
    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:
        # given 0 index 2d array, grid size m x n
        # map of the items in the shop

        # 0 is wall you can't pass through
        # 1 is empty cell that you move freely on to and from
        # all other int are price of an item in that cell
        # can move to and from these item cells

        # take 1 step to travel between adj grid cells
        # given arrays of pricing and start where pricing = [low, high]
        # star = [row, col]
        # you can start at position, and only interest in items with a price in the range of [low, high]
        # you are further given an int k

        # you are interested in the position of the k higest ranked items who prices are within the price range
        # rank is determined by 
            # distance, closer the higher rank
            # price, lower price is higher rank, of course, must be within the range
            # row number (smaller row has higher rank)
            # col number ( smaller column has higher rank)


        # same price, same distance, the one closer to the top or left or both rank higher

        # return the k highest ranked item within the price ranged sorted by their rank

        # if there are fewer than k reachable items, return all of them


        # return the list of k items that we can sort by distance, price, row then col
        

        # at each point, we skipping the wall, skipping empty space

        # we do bfs? because we can't do distance by regular distance formula
        # but we need to do step by step from the current starting point
        # at each queue, we find the distance, basically each queue loop, that should be the distance
        # we get the cells that is not equals to 0 and 1, with price within the pricing range
        # and that should be the item that we prefer
        # so we just need to do bfs because that will represent the distance
        # price is already there, row value is already there, col value is already there
        # at each value, we will need the distance, price, row and col
        # then we sort the list of prefer items, and return k items, if not enough k then return everything

        # run time: O(m x n) at worst, if there is no walls, and everything is considered as a prefer item
        # space: O(m x n) where every item is perfered, and we store all of them in a list

        # we can optimize this by checking if we already have k values in the list.

        # variables: 
        validPoints = []
        queue = deque()
        directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        result = []

        rowsCount = len(grid)
        colsCount = len(grid[0])
        visited = set()

        # add the starting point to the queue
        # then go 4 directions, check if not wall and not empty
        # add the queue, with distance + 1, price, row, col
        queue.append((0, grid[start[0]][start[1]], start[0], start[1]))
        visited.add((start[0], start[1]))

        while queue:
            for _ in range(len(queue)):
                distance, price, row, col = queue.popleft()
                for r, c in directions:
                    if (row + r, col + c) not in visited and 0 <= row + r < rowsCount and 0 <= col + c < colsCount and grid[row + r][col + c] > 0:
                        
                        queue.append((distance + 1, grid[row + r][col + c], row + r, col + c))
                        visited.add((row + r, col + c))
                        
                # now we add the point to the result, later for sorting
                if price > 1 and pricing[0] <= price <= pricing[1]:
                    validPoints.append((distance, price, row, col))
                
                
        
        for dis, val, x, y in sorted(validPoints):
            result.append([x, y])
            k -= 1
            if k == 0:
                break

        return result

69828