Golf course easy problem (code = F1) (Code Chef)

I am not able to reduce the time complexity to get a valid answer. at best i have been able to reduce the time complexity from the common O((mn)^2) to O(km*n).
The basic solution would be to check all the smaller squares inside the matrix.
i want to know the fastest way to solve the problem. Best time complexity .

k*(m-k)*n will definitely pass .

here is one easy to understand solution …

solution

the answer that you shared is of 0.98 sec and the time limit of the question is 1 sec that is it just somehow got saved. People have solved it in much lesser time than that. I am not able to understand how?
http://www.codechef.com/viewsolution/5607150
^that’s my solution

You can certainly do away with the factor k. Think in terms of having extra space to save your computation results for the next step. Also a major hint is the use of a queue.

//