AcWing 1874. 哞加密（枚举，哈希）

【题目描述】
许多人都不知道，奶牛很喜欢拼图，特别是单词拼图。
农夫约翰的奶牛最近发明了一个有趣的“单词查找器”拼图。
这种拼图的一个例子是：

USOPEN
OOMABO
MOOMXO
PQMROM

作为奶牛，它们唯一感兴趣的单词是MOO，它可以在拼图中多次沿水平、垂直、$45$度斜线或$135$度斜线出现。
上例中，MOO一共出现了$6$次。
农夫约翰也是个拼图迷，由于奶牛们不希望他在它们之前解决“单词查找器”拼图，因此它们使用”替换密码“对内容进行了加密。
该“替换密码”用不同的字母替换了字母表中的每个字母。
例如，$A$可以映射到$X$，$B$可以映射到$A$，依此类推。
没有字母映射到自身，也没有两个字母映射到同一个字母（否则解将是不明确的）。
不幸的是，奶牛忘记了替换密码的具体加密方式。
请帮助它们确定如果使用适当的替换密码解密，谜题中可能存在的最大MOO数。

【输入格式】
第一行包含$N,M$，表示拼图的尺寸为$N$行$M$列。
接下来$N$行，每行包含$M$个大写字母，形容加密后的拼图。

【输出格式】
输出如果使用适当的替换密码解密，谜题中可能存在的最大MOO数。

【数据范围】
$1\le N,M\le 50$

【输入样例】

4 6
TAMHGI
MMQVWM
QMMQSM
HBQUMQ

【输出样例】

6

【样例解释】
在此样例中，$M$和$O$分别被替换为了$Q$和$M$。
因此解密最多可存在$6$个MOO。

【分析】

我们可以将任意字母映射成另一种字母，但是不能映射成自己本身，因此所有ABB型且不为MOO的字符串均可映射成MOO。

枚举以每个点为起点，然后枚举向八个方向延伸所能构造出的长度为$3$的字符串，如果构造出的字符串$s$形如ABB，且字符串的第一个字母不为M，后两个字母不为O，那么就将字符串$s$出现的次数加一。最后所有符合要求的字符串中出现次数最多的即为答案。

【代码】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <unordered_map>
using namespace std;

const int N = 60;
char g[N][N];
unordered_map<string, int> cnt;//所有形如ABB且A不为M、B不为O的字符串数量
int n, m;
int dx[8] = {
     -1, -1, -1, 0, 1, 1, 1, 0 };
int dy[8] = {
     -1, 0, 1, 1, 1, 0, -1, -1 };

int main()
{
    
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> g[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
    
            for (int d = 0; d < 8; d++)
            {
    
                string s;
                s += g[i][j];
                int x = i, y = j;
                bool flag = true;//如果越界了则flag为false
                for (int u = 0; u < 2; u++)
                {
    
                    x += dx[d], y += dy[d];
                    if (x < 0 || x >= n || y < 0 || y >= m) {
     flag = false; break; }
                    s += g[x][y];
                }
                if (flag && s[0] != s[1] && s[1] == s[2] && s[0] != 'M' && s[1] != 'O') cnt[s]++;
            }
        }
    int res = 0;
    for (auto& [k, v] : cnt) res = max(res, v);
    cout << res << endl;
    return 0;
}