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个整数描述了该行 网格。每个整数都在该规定的位置提供了大量的食物。
样本输入：
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，但不确定这是正确的还是如何实施。如果您可以帮助建议一些算法或提供伪代码，这将非常有用。我有一个Bashy的解决方案，但在N和K的巨大价值上花费了太长时间。
更新：我的主要问题是如何在不尝试每个可能的菱形总和的情况下找到最佳的初始点。我需要以低于1毫秒的速度运行（基本上最大操作数为2.5亿）
一个O（n^2）方法是使用转换
将点旋转45度x,y -> x+y,x-y
（这也通过因子SQRT（2）缩放图像。
完成此操作后，您现在需要在正方形中找到可以通过求和区域表进行有效完成的正方形的汇总值。
这将花费O（n^2）预处理以计算积分图像，再加上O（1）以在每个正方形中找到值。有n^2个位置要测试，导致整体O（n^2）复杂性。
我并不是真正提供BFS解决方案，因为我认为这是不需要的。您会看到，您将始终能够在一个倾斜的广场上行走：
O O O O O X X X O O
O O O O X X Z X X O
O O O O O X X X O O
O O O O O O X O O O
这样，如果您的起始位置是Z。因此，基本上您只需要找到最高的倾斜正方形。
碰巧的是，写一个公式很容易写入菱形中是否包含瓷砖。只是：
abs(<center_x>) + abs(<center_y>) >= abs(<checked_tile_x>) + abs(<checked_tile_y)
然后，您将解决两个循环的结论，以检查每个图块作为中心瓷砖，而另一个将当前瓷砖添加到临时变量的循环，如果根据上述公式，当前瓷砖在菱形中。p>请注意，还有一些方法可以在菱形中的所有瓷砖上行走（如果K比平方尺寸小得多，这要高得多）。类似：
for r from -K to K:
for c from -(K - abs(r)) to (K - abs(r)):
Point is <center_y> + r, <center_x> + c