AIOC Banner

Problem: Cartography II

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


Cartography II

Input File: cartin.txt
Output File: cartout.txt
Time Limit: 0.25 second

You are responsible for governing a small chain of Pacific islands. Due to a recent economic slump you have lost the refugee processing that was your primary source of income. In search for new prosperity, it is decided that you should expand your tourism industry.

Excited by the prospect of becoming a much beloved tourist resort, you set out to discover just how long your beaches actually are. Fortunately your islands are entirely surrounded by beaches, so your task is simply to calculate the perimeter of each island.

Input

Each input file will contain a single island, represented on a rectangular map of size w by h (1 <= w,h <= 100). The first line of input will be of the form w h. Following this will be h lines, each w characters long, representing a map.

The map will be composed entirely of periods (.) and hashes (#), with periods representing ocean and hashes representing land.

Squares of land (hashes) are considered adjacent if they meet along an edge. It is possible to travel from any point on your island to any other by only moving through adjacent squares of land. Thus, of the following two maps, the first represents a single island and the second represents two different islands.

......           ......
.##...           .##...
.##...           .##...
..###.           ...##.
...##.           ...##.
......           ......

You are guaranteed that the map contains precisely one island and that this island has no inland lakes. Inland lakes are patches of water completely surrounded by land. Of the following two maps, only the first has an inland lake. In the second map the water in the centre is simply an extension of the sea, since the two squares of land in the top right hand corner are not adjacent and so the ocean flows through the gap between them.

......           ......
.####.           .###..
.##.#.           .##.#.
.##.#.           .##.#.
.####.           .####.
......           ......

Output

The output must be a single line representing the perimeter of the island. The perimeter is measured around the squares of land as illustrated below; thus the following islands have perimeters 4 and 10 respectively.

Sample Input

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

Sample Output

10

Scoring

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

 


Privacy statement
© Australian Mathematics Trust 2001-2024

Contact: training@orac.amt.edu.au
Page generated: 29 March 2024,  3:48am AEDT