Moocryption

题目描述

很多人并不知道，奶牛其实很喜欢谜题，尤其是文字谜题。\nFarmer John 的奶牛最近制作了一种有趣的“找词”谜题。一个这样的谜题例子是：\nUSOPEN\nOOMABO\nMOOMXO\nPQMROM\n\n作为奶牛，她们唯一感兴趣的单词是 “MOO”，它可以在找词谜题中出现在许多位置，可能是横向、纵向或对角线方向。上面的例子包含 6 个 MOO。\n\nFarmer John 也很喜欢文字谜题。由于奶牛不想让他在她们尝试之前就解出找词谜题，她们使用一种“替换密码”对内容进行了加密：将字母表中的每个字母替换为某个不同的字母。例如，A 可能映射到 X，B 可能映射到 A，等等。没有字母映射到它自己，并且没有两个字母映射到同一个字母（否则解密会产生歧义）。\n\n不幸的是，奶牛弄丢了解密所需的替换密码。请帮助她们确定：在选择一个合适的替换密码的情况下，这个谜题中可能存在的 MOO 的最大数量是多少。

输入格式

第一行输入包含 $N$ 和 $M$，表示谜题的行数与列数（两者都不超过 50）。接下来 $N$ 行每行包含 $M$ 个字符，描述加密后的谜题的一行。每个字符都是 A..Z 范围内的大写字母。

输出格式

请输出：若使用某个合适的替换密码进行解密，谜题中包含的 MOO 的最大可能数量。

4 6\nTAMHGI\nMMQVWM\nQMMQSM\nHBQUMQ

6

提示

这与题目开头给出的谜题是同一个，只是应用了一种密码。在这里，“M” 和 “O” 分别被替换成了 “Q” 和 “M”。\n[题目来源：Brian Dean, 2015]

标签: USACO|2015|Bronze

来源

USACO|2015|Bronze