P10752 [COI 2024] Sirologija

题目来源：。翻译来自 [文心一言](https://yiyan.baidu.com/)。如果有更好的翻译请在讨论区提供。

你是一只蚂蚁，但并非普通的蚂蚁——你是一只对奶酪学痴迷的蚂蚁！你在厨房里发现了一片新的奶酪，并希望尽可能多地派遣你的手下（小蚂蚁）去探索它。想象一下这片奶酪就像一个有 $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（15 分）：所有洞都在同一行。 - 子任务 2（18 分）：$N, M \leq 10$。 - 子任务 3（16 分）：$N, M \leq 50$，第一行、最后一行、第一列、最后一列中没有洞。 - 子任务 4（18 分）：$N, M \leq 50$。 - 子任务 5（16 分）：$N, M \leq 2000$，第一行、最后一行、第一列、最后一列中没有洞。 - 子任务 6（17 分）：没有额外的约束条件。 在所有子任务中，$2 \leq N, M \leq 2000$。