Problem: Treasure Hunt

Want to try solving this problem? You can submit your code online if you log in or register.

Treasure Hunt

Input File: cavein.txt
Output File: caveout.txt
Time Limit: 1 second

For generations stories have been told of hidden treasures deep in the caves of Rodrom. The stories are unclear as to precisely where or what the treasure is--everything from lost gold to magical elixirs have been rumoured to lie forgotten in the depths of Rodrom.

Despite the promise of wealth, not even the bravest treasure hunter has attempted to enter the crumbling caves, as renowned for their instability as for their treasures. The slightest movements in the caves cause the ceilings to come crashing down, trapping hopeful treasure hunters with no hope of rescue.

Where humans have failed, however, robots will conquer (or at least that is what you tell yourself as you put the finishing touches on your four-legged robotic cave-crawlers). Your plan is to send the courageous robots on a one-way mission into the caves to discover once and for all whether the treasure truly exists.

The caves of Rodrom can be mapped as a grid consisting of passages (shown in white) and walls (shown in gray), as follows:

$\includegraphics[scale=0.33]{grid_blank}$

Your robots enter the cave from the top-left, and can move up, down, left or right from one passage to another. Your robots are unable to squeeze through passages diagonally. Because the caves are so unstable, each time one or more of your robots leaves a passage, the ceiling of that cell collapses in preventing anything from entering that cell again.

Any single robot sent into the cave would quickly hit a dead-end and become trapped. In a moment of inspiration, you determine that if you send several robots into the cave simultaneously (spreading out as they go deeper) you will be able to explore the entire cave. For example, the cave shown above could be fully explored with four robots, as follows:

$\includegraphics[scale=0.33]{grid}$

Simplifying your task, after careful study of the maps of Rodrom you have determined that the caves have no paths that loop back to themselves. Such structures would have already collapsed centuries ago. For example, neither of the following two cave systems could exist:

$\includegraphics[scale=0.33]{grids_bad}$

While the robots are expendable, they are expensive. Your task is, given a map of the caves of Rodrom, determine the smallest number of robots needed to start off in the top left cell so that all parts of the cave can be explored.

Input

The first line of the input file will contain two integers H W, separated by a space, indicating the height and width of the cave, respectively ( 1 <= H,W <= 1000).

The next H lines will each contain W characters giving the layout of the cave. The character `#' will indicate a cave wall, while the character `.' will indicate a passage way. The entrance to the caves is always the top-left cell, and is guaranteed to be a passage way. Every passage way will be accessible from the entrance.

Output

Your output file should contain a single line containing an integer, giving the minimum number of robots required to search the entire cave. Note that even if only the top-left cell is accessible, one robot is still required to search it.

Sample Input 1

5 6
..##..
#....#
#.##.#
..#...
.#..#.

Sample Output 1

Sample Input 2

4 5
.#.##
.#...
..##.
#....

Sample Output 2

Scoring

The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.