题意理解

我们有一个 $n \times m$ 的字符网格，包含字母和空格（_）。

规则：

• 每一行有一个阅读方向：$1$ 表示从左到右，$-1$ 表示从右到左，$0$ 表示未确定。
• 每一列有一个阅读方向：$1$ 表示从上到下，$-1$ 表示从下到上，$0$ 表示未确定。
• 在确定方向后，每行/列会被空格分隔成若干个单词。
• 对于任意一行（或列），该行（列）中所有单词必须同时满足“单词字典序 $\ge$ 翻转后的字典序” 或者 同时满足“单词字典序 $\le$ 翻转后的字典序”。
• 我们想求：在所有满足条件的行列方向确定方案中，翻转后也是单词的单词种类数的最小值。
  • 如果单词 $W$ 翻转后是另一个单词 $W'$（不同），则 $W$ 和 $W'$ 各算一次。
  • 如果单词是回文，则只算一次。

关键点分析

1. 行列方向独立
   行的方向只影响行的单词顺序，列的方向只影响列的单词顺序。可以分开考虑。

2. 行/列内部的一致性约束
   对某一行 $i$，设方向为 $d_i \in \{1,-1\}$，那么这一行所有单词 $w$ 必须满足：

   • 要么 $\forall w, w \ge w^R$（字典序）
   • 要么 $\forall w, w \le w^R$ 其中 $w^R$ 是 $w$ 的反转。

   如果该行方向已固定（$d_i = 1$ 或 $-1$），则必须检查该方向下是否满足一致性条件。
   如果该行方向未固定（$d_i = 0$），我们可以选择 $1$ 或 $-1$，但必须满足一致性条件。

3. 翻转单词计数
   我们要求的是最少有多少个单词 $w$ 满足“$w^R$ 也在字典中”。
   注意：如果 $w$ 是回文，$w=w^R$，它自动满足条件，但只算一次。
   如果 $w \neq w^R$，则 $w$ 和 $w^R$ 都满足条件，所以它们都会计入答案。

   为了最小化这个数量，我们应尽量让 $w$ 和 $w^R$ 不同时出现，但受行列一致性约束的限制。

4. 最小化方法
   本质上是一个决策问题：

   • 对每个未确定方向的行/列，选择方向，使得最终所有单词集合中“$w$ 与 $w^R$ 同时出现”的对数最少。
   • 由于行列独立，可以分开处理行和列，最后合并计数。

问题抽象

设 $W$ 是最终所有单词的集合（包括行单词和列单词）。

我们想最小化： $ \sum_{w \in W} [w^R \in W \ \text{且} \ w \neq w^R] + \sum_{w \in W, w=w^R} 1 $ 但注意 $w$ 和 $w^R$ 如果成对出现，它们会分别在 $W$ 中，所以会被重复计算，除非我们小心处理。

更准确地说，定义： $S = \{w \mid w \in W, w^R \in W\}$ 我们要求 $|S|$ 的最小值？不对，因为如果 $w \neq w^R$，那么 $w$ 和 $w^R$ 都在 $S$ 中，会被算两次，但题目说“需要被分别计入”，所以就是数 $S$ 的大小。

所以目标是最小化 $|S|$。

算法思路

1. 提取所有可能的单词
   对每一行，考虑方向 $1$ 和 $-1$ 两种情况，提取单词（按空格分隔）。
   对每一列，考虑方向 $1$ 和 $-1$ 两种情况，提取单词。
   注意：方向影响单词的顺序，但不影响单词本身集合（只是反转整个行的字符串再分割），但单词会反转。

   实际上：

   • 行方向 $1$：单词是正序的。
   • 行方向 $-1$：单词是整行反转后再分割，得到的每个单词是原位置单词的反转形式。
   • 列同理。

2. 行列方向决策
   对于行 $i$，如果方向已固定，则只能取该方向对应的单词集合；如果未固定，则可以选择两个方向之一。
   列同理。

3. 一致性检查
   对某一行 $i$，如果选择方向 $d$，则得到的单词列表必须满足“所有单词 $w$ 满足 $w \ge w^R$” 或 “所有单词 $w$ 满足 $w \le w^R$”。
   注意：如果该行只有一个单词，则 $w \ge w^R$ 和 $w \le w^R$ 同时成立（因为 $w=w^R$ 或不等时必有一个成立），所以总是可行的。

4. 最小化翻转单词数
   我们选择行列方向，使得最终所有单词集合 $W$ 中，满足 $w^R \in W$ 的 $w$ 的数量最小。

   这可以建模为最小化问题，行列独立，但行列的单词会合并到 $W$ 中。

   由于 $n,m \le 72$，我们可以枚举所有行的方向组合？不行，$2^{ \#\text{未定行} } \times 2^{\#\text{未定列}}$ 可能很大，但未定行列最多 72，但实际我们可以用 DP 或贪心？其实可以行列独立处理，因为翻转单词只在行内部或列内部成对，或者行与列之间成对。

   但注意：一个单词可能同时出现在行和列中，这会影响 $w^R$ 是否出现。

已知解法思路（参考）

这是一个经典的最小化“回文对”计数问题，常用二分图建模或2-SAT：

• 对每个未确定方向的行/列，设布尔变量表示方向。
• 一致性条件可以转化为：如果某行选择方向 $d$，则必须满足 $\forall w \in \text{words}(i,d),\ w \ge w^R$ 或全部 $w \le w^R$。
• 目标是最小化 $|\{w \mid w \in W, w^R \in W\}|$。

可以证明，行列独立选择，但最终 $W$ 是行列单词的并集。
我们可以预先计算每个单词 $w$ 在哪些行/列方向选择下会出现，以及 $w^R$ 在哪些行/列方向选择下会出现。
然后问题变成：选择行列方向，使得 $w$ 和 $w^R$ 同时出现的 $w$ 的数量最小。

这可以用最小割或带权2-SAT（最小化满足条件的变量赋值）来解。

实现步骤概要

1. 提取每个行/列在两种方向下的单词集合，并检查一致性条件是否满足（不满足则禁用该方向）。
2. 建立所有不同单词的列表，并记录每个单词 $w$ 出现的（行/列，方向）条件。
3. 对每个非回文单词对 $(w, w^R)$，如果它们同时出现，会产生代价 2（因为两个都计入答案）。对回文单词 $w$，如果出现，会产生代价 1。
4. 用最小化布尔满足性问题求解，选择方向使得总代价最小。

总结

这道题是一个较复杂的组合优化问题，需要将方向选择的一致性约束和翻转单词的最小化计数结合起来，通过图论模型求解。