maximum-number-of-points-from-grid-queries

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an <code>m x n</code> integer matrix <code>grid</code> and an array <code>queries</code> of size <code>k</code>.

Find an array <code>answer</code> of size <code>k</code> such that for each integer <code>queries[i]</code> you start in the top left cell of the matrix and repeat the following process:

<ul>
	<li>If <code>queries[i]</code> is strictly greater than the value of the current cell that you are in, then you get one point if it is your first time visiting this cell, and you can move to any adjacent cell in all <code>4</code> directions: up, down, left, and right.</li>
	<li>Otherwise, you do not get any points, and you end this process.</li>
</ul>

After the process, <code>answer[i]</code> is the maximum number of points you can get. Note that for each query you are allowed to visit the same cell multiple times.

Return the resulting array <code>answer</code>.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2025/03/15/image1.png" style="width: 571px; height: 152px;" />
<pre>
Input: grid = [[1,2,3],[2,5,7],[3,5,1]], queries = [5,6,2]
Output: [5,8,1]
Explanation: The diagrams above show which cells we visit to get points for each query.</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2022/10/20/yetgriddrawio-2.png" />
<pre>
Input: grid = [[5,2,1],[1,1,2]], queries = [3]
Output: [0]
Explanation: We can not get any points because the value of the top left cell is already greater than or equal to 3.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>2 &lt;= m, n &lt;= 1000</code></li>
	<li><code>4 &lt;= m * n &lt;= 105</code></li>
	<li><code>k == queries.length</code></li>
	<li><code>1 &lt;= k &lt;= 104</code></li>
	<li><code>1 &lt;= grid[i][j], queries[i] &lt;= 106</code></li>
</ul>

maxPoints

Maximum Number of Points From Grid Queries

Trapping Rain Water II

trapping-rain-water-ii

接雨水 II

Escape the Spreading Fire

escape-the-spreading-fire

逃离火灾

Breadth-First Search

Union Find

Array

Two Pointers

Matrix

Sorting

Heap (Priority Queue)

给你一个大小为 <code>m x n</code> 的整数矩阵 <code>grid</code> 和一个大小为 <code>k</code> 的数组 <code>queries</code> 。

找出一个大小为 <code>k</code> 的数组 <code>answer</code> ，且满足对于每个整数 <code>queries[i]</code> ，你从矩阵 左上角 单元格开始，重复以下过程：

<ul>
	<li>如果 <code>queries[i]</code> 严格 大于你当前所处位置单元格，如果该单元格是第一次访问，则获得 1 分，并且你可以移动到所有 <code>4</code> 个方向（上、下、左、右）上任一 相邻 单元格。</li>
	<li>否则，你不能获得任何分，并且结束这一过程。</li>
</ul>

在过程结束后，<code>answer[i]</code> 是你可以获得的最大分数。注意，对于每个查询，你可以访问同一个单元格 多次 。

返回结果数组 <code>answer</code> 。

&nbsp;

示例 1：
<img alt="" src="https://assets.leetcode.com/uploads/2025/03/15/image1.png" style="width: 571px; height: 152px;" />
<pre>
输入：grid = [[1,2,3],[2,5,7],[3,5,1]], queries = [5,6,2]
输出：[5,8,1]
解释：上图展示了每个查询中访问并获得分数的单元格。</pre>

示例 2：
<img alt="" src="https://assets.leetcode.com/uploads/2022/10/20/yetgriddrawio-2.png" />
<pre>
输入：grid = [[5,2,1],[1,1,2]], queries = [3]
输出：[0]
解释：无法获得分数，因为左上角单元格的值大于等于 3 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>2 &lt;= m, n &lt;= 1000</code></li>
	<li><code>4 &lt;= m * n &lt;= 105</code></li>
	<li><code>k == queries.length</code></li>
	<li><code>1 &lt;= k &lt;= 104</code></li>
	<li><code>1 &lt;= grid[i][j], queries[i] &lt;= 106</code></li>
</ul>