题目背景

题目来源：https://hsin.hr/hio2024/。翻译来自 文心一言。如果有更好的翻译请在讨论区提供。

题目描述

你是一只蚂蚁，但并非普通的蚂蚁——你是一只对奶酪学痴迷的蚂蚁！你在厨房里发现了一片新的奶酪，并希望尽可能多地派遣你的手下（小蚂蚁）去探索它。想象一下这片奶酪就像一个有 $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$ 值。

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

3

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

1

3 2
.#
#.
..

0

提示

【数据范围】

• 子任务 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$。