|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||8||2||2||25.000%|
Once upon a time, on the island inhabited by Lilliput, a great traveler Gulliver was woken up by the cheering of the above mentioned people. After the initial struggle, Lilliputans started telling him about their war with the inhabitants of the neighboring island, Blefuscu.
It is little known that Blefuscu and Lilliput once lived on the same island. After someone had baked an egg, the two nations couldn’t agree which side they should start eating the egg on. The war escalated so much that they decided to split the island in two. The South side was taken by Blefuscu, and the Northside was taken by Lilliput.
Miraculously, the island’s shape was rectangular, composed of R×C square parcels. Some of the parcels were already underwater, and the citizens decided to flood some other parcels. The island was to be divided into at least two parts, one of which would contain the entire top row (the North side) and the other part the entire bottom row (the South side). Two parcels that aren’t underwater belong to the same part of the island if one can get from one to the other by moving up, down, left and right.
For example, if the left image below shows the island before the incident (the black parcels were already underwater), then to separate the island, only two more parcels need to be divided, as in the right image.
The historic problem that people have been talking about for generations is: what was the least number of parcels that had to be flooded to completely separate the two parts of the island? Your task is to write the program which computes that number.
The first line of input consists of two numbers, R and C (3 ≤ R, C ≤ 1 000), the number of rows and columns the island consists of.
Each of the following R lines contains C characters, either '.' or '#'. The '#' sign represent underwater parcels. The input will be such that all of the parcels that aren’t underwater are connected and no parcels are flooded in the top and bottom rows.
Output the number of parcels that need to be flooded to separate the two parts of the island.
4 5 ..... ..#.. .#..# .....