The grid is m*n not n*m

The problem asks you to find the diameter of a tree.

Try this test:
4 3
####
#..#
####
Answer is 1 :)

If the matrix size is 3, with the given contraints, it won't be "2 special cells", because 8 of them will be walls, and will be only one free cell. Could be that those special cells were located at the same place? Please drop some light on that. Thanks

cin>>n>>m
not while(cin>>n>>m)

Memory limit was changed from 16 MB to 64 MB. 12 authors have got AC after rejudge.

Test generated by the following program is hard for recursive solutions on some languages. For example Java recursive solution uses approx 31M of stack on this test while the whole ML of this problem is 16M.

Very very strange that the test set does not contain test with maximal possible answer.

const
   height = 1000;
   width = 1000;
var
   line, column : integer;
begin
   writeln(height, ' ', width);
   for line := 1 to height do begin
      for column := 1 to width do begin
         if
            (line = 1) or (line = height) or
            (column = 1) or (column = width) or
            (line mod 4 = 1) and (column > 2) or
            (line mod 4 = 3) and (column < width - 1)
         then begin
            write('#');
         end
         else begin
            write('.');
         end;
      end;
      writeln;
   end;
end.

Edited by author 09.01.2009 17:29

I always got Stack Overflow on test 6, help!

[code deleted]

Edited by moderator 13.02.2007 20:52

Use simulation with a big array...
I got AC with int[50000][3] in 0.156s in Java.

Can this be done with O(N) memory ?

Trying to solve this simple problem and always get WA1. Tried to read input by chars/by lines. Tried to output with endline and without...

Got some questions.
What is correct answer for:
3 3
###
#.#
###

...and for:
3 3
###
###
###

...is such input correct:
3 3
#.#
...
#.#

May be i'm on wrong way - my algo is - create a list of leaves of tree; delete them and increment counter; repeat until leaves list is empty. answer is doubled counter - 1 or doubled counter if one vertex left in tree.

...The next lines describe the labyrinth. The ith line of the next m lines contains n characters. Each character is either "#" or ".", with "#" indicating a forbidden cell, and "." indicating a free cell (i = 1, 2, ..., m)...

But in sample input the last character in the 1st line of labyrinth is space.