# 种西瓜

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

## 背景故事

村长习惯把西瓜种成整齐的长列，新来的农夫却设计了一块形状不规则的瓜田。瓜藤会争用旁边的空地，而生长顺序和方向都无法控制。请帮他们算出这块瓜田最终最多或最少能结出多少个西瓜。

## 形式化问题描述

瓜田是 $n$ 行 $m$ 列的网格。每格初始为瓜藤 `l` 、空地 `o` 或障碍物 `x` ；网格外视为障碍物。

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

不断生长，直到没有瓜藤还能结瓜。给定类型 $tp$ ：$tp=0$ 时求所有可能终止状态中的最大结瓜数；$tp=1$ 时求最小结瓜数。

## 输入格式

第一行三个整数 $n,m,tp$ .接下来 $n$ 行，每行一个长度为 $m$ 的字符串，表示瓜田。

## 输出格式

输出一个整数，表示要求的最大值或最小值。

## 样例 1

### 输入

```text
2 5 0
xlolx
xolox
```

### 输出

```text
3
```

## 样例 2

### 输入

```text
2 5 1
xlolx
xolox
```

### 输出

```text
2
```

## 样例 3

### 输入

```text
1 3 1
lxl
```

### 输出

```text
0
```

## 样例解释

前两个样例使用同一块瓜田。左图三株瓜藤分别结瓜，得到三个瓜；右图中上方两株瓜藤共用的空地已被占用，剩余未结瓜的瓜藤无法继续生长，最终只有两个瓜。第三组中没有空地，答案为零。

![同一块瓜田的三瓜与两瓜终止状态，箭头从瓜藤指向瓜](assets/harvest.svg)

图中 `l` 表示瓜藤，`o` 表示空地，`x` 表示障碍，带圆圈的 `M` 表示瓜。箭头给出结瓜关系。

## 数据范围与保证

所有数据满足 $n,m\ge1$ ，$tp\in\{0,1\}$ .当 $tp=0$ 时，$nm\le1000$ ；当 $tp=1$ 时，$nm\le100$ 且瓜藤数不超过 $18$ .允许没有瓜藤或没有空地。

| 分值比例 | 额外条件          |
| ---- | ------------- |
| 20%  | $tp=0$ ，$n=1$ |
| 30%  | $tp=0$        |
| 20%  | $tp=1$ ，$n=1$ |
| 30%  | $tp=1$        |