Problem 113: Chicken Across

(U.M. ACM Runoffs 2002, problem 6)

Description

      Microscopic chickens have infected the crossword in the Sunday paper. They originally infected the topmost leftmost blank square, and reproduce at such a rate that every day every blank square that is neighbouring an already infected square becomes infected itself. Black ink is contains antibiotics, so the black squares are never infected or crossed. How long will it be until the last blank square is covered with chickens?

      The input to your program will be a rectangular (not necessarily square) grid of characters representing the shape of the crossword puzzle. The gish '#' character represents a black square, and a space represents a blank. There will never be more than 100 rows or columns, or fewer than 1. All rows/lines of the puzzle will be of exactly the same length, spaces at the ends of lines will not be trimmed away.

      On day zero, only one square is infected, and it is always the leftmost blank square on the topmost line that has any blank squares. It takes exactly one day for the chicken infection to spread from all the already infected squares to all neighbouring uninfected blank squares. The chicken infection is bounded by the edge of the puzzle; it can not sneak around the edges.

      The diagram below shows the progression of the infection in one sample crossword, the numbers show the day on which each blank square is infected. As you can see, the last three blank squares will all become infected after 20 days, so for this example the answer would be 20. The output from your program should be either a single integer giving the number of days until total infection, or the word "Never" if some of the blank squares will always remain free of chickens.

Sample Input

## ## ##
    # # 
 # ## # 
 ##     
     ## 
 # ## # 
 # #    
## ## ##

Sample Output

20

End of Problem