Guliver

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 North side 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.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.