[AdditionalFile5513.zip](file://AdditionalFile5513.zip?type=additional_file)

#5513. 「COI 2024」Sirologija

标签: 传统 | 时间限制: 1000 ms | 内存限制: 1024 MiB |

题目描述

译自 COI 2024 T4「Sirologija」

你是一只蚂蚁，但不是普通的蚂蚁——你是一只痴迷于奶酪学的蚂蚁！

你厨房里发现了一块新的奶酪，想派尽可能多的小兵去探索它。想象一下这块奶酪是一个 $N$ 行 $M$ 列的表格，行从上到下编号为 $1$ 到 $N$，列从左到右编号为 $1$ 到 $M$。有些格子包含洞，而有些则包含奶酪。我们将第 $r$ 行第 $s$ 列的格子表示为 $(r, s)$。左上角和右下角的格子一定会包含奶酪。

假设小兵的数量为 $K$。你的小兵将从左上角的格子开始探索，并在右下角的格子结束。他们只能向下和向右移动。此外，他们的路径不能「交叉」，这意味着我们可以给他们分配从 $1$ 到 $K$ 的标签，使得不存在某个格子，从该格子出发，编号较小的小兵向右移动，而编号较大的小兵向下移动。

而且，你希望这些路径在某种意义上是「不同」的，这意味着对于任意两个小兵，都存在一个包含洞的格子 $(r, s)$，使得其中一个小兵在某个时刻位于第 $s$ 列且行号小于 $r$ 的位置，而另一个小兵在某个时刻（不一定同时）位于第 $s$ 列且行号大于 $r$ 的位置。非正式地说，每对小兵都从不同的方向接近了某个洞。

请输出 $K$ 的最大值，使得存在满足给定条件的小兵路径选择。

以下是一些不满足条件的路径示例：

上图是一个无效的路径选择：它们相交了

上图也是一个无效的路径选择：它们从同一侧接近了洞

输入格式

第一行包含正整数 $N, M$。

接下来的 $N$ 行包含表格行的描述。第 $i$ 行包含 $M$ 个字符，其中 . 表示奶酪，# 表示包含洞的格子。

输出格式

在单独一行中输出小兵数量 $K$ 的最大可能值。

样例 1

输入

5 5
.....
.#...
.....
...#.
.....

输出

3

样例 $1$ 的路径示例如下：

样例 2

输入

5 5
....#
....#
.....
.....
#....

输出

1

样例 $2$ 的路径示例如下：

样例 3

输入

3 2
.#
#.
..

输出

0

数据范围与提示

对于所有输入数据，满足 $2 \leq N, M \leq 2000$。

详细子任务附加限制及分值如下表所示：