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, then that space doesn’t require a fence. For example:
........ 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.
- . – empty location
- # – an animal
The output file OUT4.txt will contain 5 lines of output. Each denotes the amount of fencing required to completely enclose all animals in the scheme described above.
5
#.#..
.##..
.....
.#..#
...#.
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.