Analysis: The Lazy Cow [Silver] by Fatih Gelgi

The straightforward idea is to try brute-force: for each cell (r,c), calculate the amount of grass in K steps. This approach requires O(N^2 K^2) which is slow considering the given bounds in the problem. A simple observation is that we don't need to recalculate the sum of the square region each time. Instead we can slide it by removing the values of former cells and adding values of new cells. The number of cells to remove and add is O(K) as opposed to O(K^2).

Note that the reachable cells from a cell compose a square of size K which is tilted 45 degrees. How to slide that tilted square? While sliding a square is simple, this one seems rather complicated. An idea is to rotate the grid instead of rotating the sliding window as shown in the example below:

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

Now we can slide it easily by subtracting the first column in the region from the sum and adding the next column after the region to the sum. Note that the matrix includes non-lattice points too (i.e. extra zeros in the matrix). Bessie can be positioned in lattice points only; that needs an extra check.

In this approach, the complexity is reduced to O(KN^2). The required memory becomes 4 times more but it is not a trouble since N is small. Although the solution can have further optimization, this one is rather easy to implement and more than sufficient for the problem. A sample code is provided below:

#include <fstream>

#define MAX 801

using namespace std;

int n,k,mat[MAX][MAX],best;

int main()
{
	ifstream fin("lazy.in");
	fin >> n >> k;
	// rotate the matrix 45 degrees
	for (int i=0; i<n; i++)
		for (int j=0; j<n; j++)
			fin >> mat[i+j][n-i+j-1];
	fin.close();

	// 45 degree rotation expands the size of the matrix
	// it also includes the cells with half distance
	int t=(n+1)%2;	// t is used to avoid non-lattice points
	n=n*2-1;
	for (int i=0; i<n; i++,t=1-t)
	{
		// calculate the sum of 2k x 2k region
		// Bessie can only be positioned in lattice points
		int sum=0;
		for (int a=max(i-k,0); a<n && a<=i+k; a++)
			for (int b=max(t-k,0); b<n && b<=t+k; b++)
				sum+=mat[a][b];
		if (best<sum) best=sum;

		// slide the region
		for (int j=t+1; j+k<n; j++)
		{
			for (int a=max(i-k,0); a<n && a<=i+k; a++)
			{
				if (j-k-1>=0) sum-=mat[a][j-k-1];
				sum+=mat[a][j+k];
			}
			// update the sum only in lattice points
			if (j%2==t && best<sum) best=sum;
		}
	}

	ofstream fout("lazy.out");
	fout << best << endl;
	fout.close();
}