Choosing Best Possible Initial Location in Graph to Maximize Potential Neighbors

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.

Suppose the grid is as follows, where (Y) describes your initial position (here, in row 3, column 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    

When the value of K is 2, you can only reach the locations marked with *s.

Determine the maximum amount of food you can reach, if you chooses the best possible initial location in the grid.

INPUT FORMAT:

• Line 1: The integers N and K.

• Lines 2..1+N: Line r+1 contains N integers describing row r of the grid. Each integer gives the amount of food in that prescribed location.

SAMPLE INPUT:

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

OUTPUT FORMAT:

• Line 1: The maximum amount of food you can reach, if you choose the best possible initial location (the location from which you can reach the most food).

SAMPLE OUTPUT:

342

DETAILS:

In the example above, you can reach 342 total units of food if you locate yourself in the middle of the grid. This is the maximum amount of food you can reach.

My Ideas:

I was thinking of using some approach using Breadth-First Search as each step has the same cost of 1, but am not sure if this correct or how to implement it. If you could help suggest some algorithm or give pseudo code that would be extremely helpful. I have a bashy solution but takes much too long on big values of N and K. I'm trying to get this to run under 1 ms for large cases of N and K.

UPDATE: The main question I have is how to find the best initial point to start of with without trying each possible rhombus sum. I need this to run in under 1 millisecond (basically max number of operations should be 250 million)

Answer 1

One O(N^2) approach is to rotate the points by 45 degrees using the transform

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

(This also scales the image by a factor sqrt(2)).

Once you have done this, you now need to find the summed value in a square which can be done efficiently by using a summed area table.

This costs O(N^2) preprocessing to compute the integral image, plus O(1) to find the value in each square. There are N^2 positions to test, resulting in an overall O(N^2) complexity.

Answer 2

I'm not really giving a BFS solution, because I don't think that's necessary. You see, you'll always be able to walk in a tilted square:

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

Like this, in case your starting position was the Z. So basically you just have to find the tilted square with the highest sum.

As it happens, it's rather easy to write a formula whether a tile is included in the rhombus. It's just:

abs(<center_x>) + abs(<center_y>) >= abs(<checked_tile_x>) + abs(<checked_tile_y)

Then you'll solution will conclude two for loops for checking each tile as center tile, and another to which add the current tile to a temporary variable if, according to above formula, the current tile is in the rhombus.

Mind you that there are also ways to just walk over all tiles in the rhombus (which is far more efficient if K is a lot smaller than the square size). Something like:

for r from -K to K:
    for c from -(K - abs(r)) to (K - abs(r)):
        Point is <center_y> + r, <center_x> + c