If you use Java pay attention to size of arrays, that you used.
I used 2 arrays for saving current line and prev line of input(every has o(n) elements), and 2 arrays for saving result of calculating in prev Line, and for saving result of calculation in current line (every has o(n) elements).

Edited by author 21.02.2010 15:56

This problem is not so memory consuming. Java solution using variable
char field[][] = new char[1 + n + 1][1 + n + 1];
gets AC.

So it is possible to store whole input in memory, but it is impossible to store significant amount of data for each cell. For example 4 arrays NxN of 16-bit ints need extra 16 Mb of memory while total ML is 16 Mb.