The Government has a Limited Supply of Walls Introduction

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.

Problem

Our doomsday scenario is described by two numbers on a single line, n and 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.


x Impassable. 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.
o Encampment. 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.

Example Input

 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


Example Output

3


Assumptions


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 &lt; n &lt; 16
2 &lt; m &lt; 16
Input may be provided from stdin, read from "city.txt", or accepted as a single argument


Shortest code wins!
Mathematica, 257 253 chars
d=&quot;city.txt&quot;~Import~&quot;Table&quot;;g=EdgeAdd[#,∞&lt;-&gt;Tr@#&amp;/@Position[VertexDegree@#,2|3]]&amp;@GridGraph@d[[1,{2,1}]];{o,x,s}=Tr/@Position[Join@@d[[2;;]],#]&amp;/@{&quot;o&quot;,&quot;x&quot;,&quot;.&quot;};Catch@Do[If[Min[GraphDistance[VertexDelete[g,x⋃w],∞,#]&amp;/@o]==∞,Throw@Length@w],{w,Subsets@s}]

Input is read from &quot;city.txt&quot;.
Explanation:
Mathematica has many functions to deal with graphs.
First, I read the data from &quot;city.txt&quot;.
d=&quot;city.txt&quot;~Import~&quot;Table&quot;;

Then I construct a grid graph with 'm'*'n' vertices (GridGraph@d[[1,{2,1}]]), and add to it a &quot;vertex at infinity&quot; which is connected to every vertex on the &quot;edges&quot; of the graph. This vertex is where the water flow from.
g=EdgeAdd[#,∞&lt;-&gt;Tr@#&amp;/@Position[VertexDegree@#,2|3]]&amp;@GridGraph@d[[1,{2,1}]];

And o, x and s denote the positions of &quot;o&quot;, &quot;x&quot; and &quot;.&quot; respectively.
{o,x,s}=Tr/@Position[Join@@d[[2;;]],#]&amp;/@{&quot;o&quot;,&quot;x&quot;,&quot;.&quot;};

Then for any subset w of s (the subsets are sorted by length), I delete the vertices in x and w from g (VertexDelete[g,x⋃w]), and find the length of the shortest path from the &quot;vertex at infinity&quot; to the encampment o. If the length is infinity, then the encampment will be safe. So the length of the first such w is the minimum number of walls required to protect an encampment.
Catch@Do[If[Min[GraphDistance[VertexDelete[g,x⋃w],∞,#]&amp;/@o]==∞,Throw@Length@w],{w,Subsets@s}]