The Government has a Limited Supply of Walls
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}]