algorithm - 在图中选择最佳可能的初始位置以最大化潜在邻居

Question

A grid is described by an N by N grid of square cells  (1 <= N <= 400).
The cell in row r and column c (1 <= r,c <= N) contains
x units of food (0 <= x <= 1000).  From some initial square in
the grid, you are only willing to take up to K steps (0 <= K <= 2*N).
Each step you take moves you to a cell that is directly north, south,
east, or west of your current location.

假设网格如下，其中(Y)描述了你的初始位置(此处为第 3 行第 3 列):

50    5     25*   6     17    
14    3*    2*    7*    21    
99*   10*   1*(B) 2*    80*    
8     7*    5*    23*   11  
10    0     78*   1     9    

当K的值为2时，只能到达标有*s的位置。

确定你能拿到的最大食物量，如果您选择网格中可能的最佳初始位置。

输入格式:

• 第 1 行:整数 N 和 K。

• 第 2..1+N 行:第 r+1 行包含 N 个整数，描述了第 r 行 网格。每个整数表示指定位置的食物量。

示例输入:

5 2
50 5 25 6 17
14 3 2 7 21
99 10 1 2 80
8 7 5 23 11
10 0 78 1 9

输出格式:

• 第 1 行:您可以选择的最大食物量 最佳可能的初始位置(从哪个位置开始 你可以获得最多的食物)。

示例输出:

342

详情:

在上面的例子中，如果你能吃到 342 个食物单位将自己定位在网格的中间。这是您可以拿到的最大食物量。

我的想法:

我正在考虑使用某种使用广度优先搜索的方法，因为每个步骤的成本都为 1，但我不确定这是否正确或如何实现。如果您可以帮助建议一些算法或提供非常有用的伪代码。我有一个笨拙的解决方案，但在 N 和 K 的大值上花费的时间太长。对于 N 和 K 的大情况，我试图让它在 1 毫秒内运行。

更新:我的主要问题是如何在不尝试每个可能的菱形和的情况下找到最佳初始点。我需要它在 1 毫秒内运行(基本上最大操作数应该是 2.5 亿)

Answer 1

一种 O(N^2) 方法是使用变换将点旋转 45 度

x,y -> x+y,x-y

(这也通过因子 sqrt(2) 缩放图像)。

完成此操作后，您现在需要在正方形中找到求和值，这可以通过使用 summed area table 高效地完成。 .

这需要 O(N^2) 的预处理来计算积分图像，加上 O(1) 的时间来找到每个方 block 中的值。有 N^2 个位置需要测试，导致整体复杂度为 O(N^2)。