P15954 [ICPC 2018 Jakarta R] Icy Land

你有一个 $R$ 行 $C$ 列的棋盘，每个格子要么是干地（'#'），要么是冰地（'.'）。你可以在棋盘上向四个方向（北、南、东、西）之一移动。 你可以在任何干地上行走或停留，没有任何问题；但冰地非常滑。如果你站在格子 $(r, c)$ 并决定向某个方向移动，那么你会沿着该方向一直滑动，直到到达一块干地或棋盘边界。 例如，考虑下面这个 6 行 7 列的棋盘： ``` #...... .#..... ..##... ..##... ....... .#..... ``` - 从 $(1, 3)$（第 1 行第 3 列）向南移动，你会停在 $(3, 3)$。 - 从 $(4, 4)$ 向北移动，你会停在 $(3, 4)$。 - 从 $(1, 1)$ 向东移动，你会停在 $(1, 7)$。 - 从 $(6, 5)$ 向西移动，你会停在 $(6, 2)$。 假设你的初始位置是 $(3, 7)$，移动序列依次为西、西、西、南、东、北、西、西。那么你的位置变化为：$(3, 7) \rightarrow (3, 4) \rightarrow (3, 3) \rightarrow (3, 1) \rightarrow (6, 1) \rightarrow (6, 2) \rightarrow (2, 2) \rightarrow (2, 1) \rightarrow (2, 1)$，因此你访问了 $8$ 个不同的格子。注意 $(2, 1)$ 被访问了两次。在移动过程中仅经过而未停留的格子不算作被访问，例如在上面的例子中，从 $(3, 1)$ 向南移动时，你会经过 $(4, 1)$ 和 $(5, 1)$，最终到达 $(6, 1)$；因此，在该次移动中 $(4, 1)$ 和 $(5, 1)$ 不被视为被访问，只有 $(3, 1)$ 和 $(6, 1)$ 算作被访问。 你可以将任意冰地改为干地，你的目标是确保 **无论** 初始起始位置如何，你都能访问棋盘上的 **所有** 格子；换句话说，虽然你还不知道起始位置，但给定棋盘后，你要确保能够实现目标。请问，为了确保能够实现目标，你至少需要改变多少个格子？

输入的第一行包含两个整数 $R$ 和 $C$（$1 \leq R, C \leq 500$），分别表示棋盘的行数和列数。接下来的 $R$ 行，每行包含 $C$ 个字符，表示给定的棋盘。每个字符要么是 '#'（表示干地），要么是 '.'（表示冰地）。

输出一行一个整数，表示为了确保无论初始起始位置如何，都能访问棋盘上所有格子，至少需要改变的格子数。

**样例输入/输出的解释** 我们只需要改变格子 $(3, 3)$。 ``` .... .### ###. ###. ``` 令 'N' 表示北，'S' 表示南，'W' 表示西，'E' 表示东。 - 如果从 $(1, 1)$ 开始，移动序列 "SSENNWENSESSEWNENWNE" 将访问所有格子。对应的位置变化为： $(1, 1) \rightarrow (3, 1) \rightarrow (4, 1) \rightarrow (4, 2) \rightarrow (3, 2) \rightarrow (2, 2) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (4, 3) \rightarrow (4, 4) \rightarrow (4, 3) \rightarrow (3, 3) \rightarrow (3, 4) \rightarrow (2, 4) \rightarrow (2, 3) \rightarrow (1, 3) \rightarrow (1, 4)$。 - 如果从 $(1, 2)$ 开始，先移动 "W"，然后执行上面第一个例子中的移动序列（"SSENNWENSESSEWNENWNE"），即可访问所有格子。对应的位置变化为：$(1, 2) \rightarrow (1, 1) \rightarrow \ldots$ - 如果从 $(1, 3)$ 开始，先移动 "W"，然后执行上面第一个例子中的移动序列，即可访问所有格子。对应的位置变化为：$(1, 3) \rightarrow (1, 1) \rightarrow \ldots$ - $\ldots$ - 如果从 $(4, 3)$ 开始，先移动 "NNNW"，然后执行上面第一个例子中的移动序列，即可访问所有格子。对应的位置变化为：$(4, 3) \rightarrow (3, 3) \rightarrow (2, 3) \rightarrow (1, 3) \rightarrow (1, 1) \rightarrow \ldots$ - 如果从 $(4, 4)$ 开始，先移动 "NNW"，然后执行上面第一个例子中的移动序列，即可访问所有格子。对应的位置变化为：$(4, 4) \rightarrow (2, 4) \rightarrow (1, 4) \rightarrow (1, 1) \rightarrow \ldots$ 翻译由 DeepSeek V3.2 完成