种西瓜 3¶

参考时间限制：0.5 秒（参考环境：评测环境与性能；仅供预估）
实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
内存限制：128 MB

背景故事¶

沿着村边的小路，农夫开垦了一片狭长的瓜田。瓜藤会争用身边的空地，生长顺序和方向都无法控制。农夫想估计最差的收成：等整片瓜田再也长不出新瓜时，至少会有多少个瓜？

(本故事由GPT-6重写)

瓜田是 \(n\) 行 \(m\) 列的网格。每格初始为瓜藤 l 、空地 o 或障碍物 x ；网格外视为障碍物。瓜田较窄，满足 \(\min(n,m)\le8\) ，瓜藤数量没有额外上限。

每株瓜藤至多结一个瓜。一次生长可以选择任意一株尚未结瓜、且上下左右至少有一格空地的瓜藤，在其中一格空地生成一个瓜。这个格子此后被占用，不能再长瓜。瓜藤所在格子始终是瓜藤，不能用来长瓜。

不断生长，直到没有瓜藤还能结瓜。求所有可能终止状态中的最小结瓜数。必须达到上述终止条件，不能在仍有生长机会时提前停止。

第一行两个整数 \(n,m\) .接下来 \(n\) 行，每行一个长度为 \(m\) 的字符串，表示瓜田。

输出一个整数，表示终止时可能达到的最少结瓜数。

2 5
xlolx
xolox

1 6
lololo

1 3
lxl

4 1
l
o
l
o

第一组可让左上方瓜藤向中上方空地结瓜，再让下方瓜藤向其右侧空地结瓜。剩余未结瓜的瓜藤旁边已经没有空地，得到两个瓜。一个瓜不能让所有瓜藤停止生长。

第一组样例中两个瓜的终止状态

图中箭头从瓜藤指向它结出的瓜，带圈的 M 表示瓜；其他字母与输入字符含义一致。

第二组可让第 \(1\) 格瓜藤向第 \(2\) 格结瓜、第 \(5\) 格瓜藤向第 \(4\) 格结瓜，此时第 \(3\) 格瓜藤无法继续生长，答案为 \(2\) .第三组没有空地，答案为零。第四组让第 \(3\) 格瓜藤向第 \(2\) 格结瓜即可终止，答案为 \(1\) .

本题数据范围由 Codex（GPT-6）加强并重新设计：最小值问题的网格面积上限由 \(100\) 提高到 \(5000\) ，取消瓜藤数至多 \(18\) 的额外限制，同时限定较短边不超过 \(8\) .

所有数据满足 \(n,m\ge1\) 、\(nm\le5000\) 、\(\min(n,m)\le8\) .每个网格字符都属于 l 、o 、x .允许没有瓜藤或没有空地，也允许存在互不相连的区域。