DWITE
February 2013
Problem 4
Fencing Problems

In a typical "build a fence" scenario, farmer John needs to fence his animals in the cheapest way possible. In this case, "the cheapest" is defined as keeping them in the smallest area possible. (Well, somebody is buying those non-free-range products...) You observe that while it's simple to just box every marked location at the perimeter, some of the fencing is redundant. To be specific, if two perimeter non-corner segments overlap, than that space doesn't require a fence. E.g.

........    FFFFFFFF
.#.#..#. => F#.#FF#F
........    FFFFFFFF 
		

Wanting to enclose # locations, the only empty space remaining is the omitted fence. The rightmost # is completely enclosed (you can imagine that FF leaves enough space to have a pathway in between). Make sure to think through all the various configurations that might need to be fenced.

The input file DATA4.txt will contain 5 test cases. Each case will start with a line containing a single number 1 <= N <= 15 representing the length of the side of John's square farm, followed by N lines describing the layout of the animals.

The output file OUT4.txt will contain 5 lines of output. Each denotes the amount of fencing required to completely enclose all animals as described above.

Sample Input (first case shown):
 
5
#.#..
.##..
.....
.#..#
...#.
		        
Sample Output (first case shown):
 
25
		        
Sample Explanation - the outside of the grid must still be fenced:
FFFFF..
F#.#F..
FF##F..
.F.FFFF
.F#F.#F
.FFF#FF
...FFF.