Knowledgeable code golfers prepared us for the doomsday flood. Areas at risk were evacuated, and the population moved to high ground.
We underestimated the flood (or perhaps there was a bug in @user12345's code). Some high-ground areas are rapidly approaching sea level. Walls must be erected in order to ensure the survival of the now densely populated encampments. Sadly, the government has a limited supply of walls.
Our doomsday scenario is described by two numbers on a single line,
m. Following that line are
n lines with
m values per line, separated only by a single space. Each value will be one of four characters.
xImpassable. Water cannot flow here. Walls cannot be erected here.
-Unstable. Water can flow through this here. Walls cannot be erected here.
.Stable. Water can flow through here. Walls can be erected here.
oEncampment. Water can flow through here. If it does, everyone dies. Walls cannot be built here.
Water will flow from all edges of the map, unless the edge is impassable or a wall is constructed on the tile. Write a program that can output the minimum number of walls required to protect an encampment.
6 7 x . . x x x x x . . x - - x x . x x - - x x . o o o - . x . o o o - . x x x x x x x
- Water only flows orthogonally
- Encampments only exist as one orthonagonally contiguous block per scenario
- A solution will always exist (although it may require copious amounts of walls)
- Encampments cannot be located on an edge, as the scenario would then have no solution
- 2 <
- 2 <
- Input may be provided from stdin, read from "city.txt", or accepted as a single argument
Shortest code wins!