当前位置:网站首页>AcWing 1874. 哞加密(枚举,哈希)
AcWing 1874. 哞加密(枚举,哈希)
2022-04-23 11:18:00 【柃歌】
【题目描述】
许多人都不知道,奶牛很喜欢拼图,特别是单词拼图。
农夫约翰的奶牛最近发明了一个有趣的“单词查找器”拼图。
这种拼图的一个例子是:
USOPEN
OOMABO
MOOMXO
PQMROM
作为奶牛,它们唯一感兴趣的单词是MOO
,它可以在拼图中多次沿水平、垂直、 45 45 45度斜线或 135 135 135度斜线出现。
上例中,MOO
一共出现了 6 6 6次。
农夫约翰也是个拼图迷,由于奶牛们不希望他在它们之前解决“单词查找器”拼图,因此它们使用”替换密码“对内容进行了加密。
该“替换密码”用不同的字母替换了字母表中的每个字母。
例如, A A A可以映射到 X X X, B B B可以映射到 A A A,依此类推。
没有字母映射到自身,也没有两个字母映射到同一个字母(否则解将是不明确的)。
不幸的是,奶牛忘记了替换密码的具体加密方式。
请帮助它们确定如果使用适当的替换密码解密,谜题中可能存在的最大MOO
数。
【输入格式】
第一行包含 N , M N,M N,M,表示拼图的尺寸为 N N N行 M M M列。
接下来 N N N行,每行包含 M M M个大写字母,形容加密后的拼图。
【输出格式】
输出如果使用适当的替换密码解密,谜题中可能存在的最大MOO
数。
【数据范围】
1 ≤ N , M ≤ 50 1≤N,M≤50 1≤N,M≤50
【输入样例】
4 6
TAMHGI
MMQVWM
QMMQSM
HBQUMQ
【输出样例】
6
【样例解释】
在此样例中, M M M和 O O O分别被替换为了 Q Q Q和 M M M。
因此解密最多可存在 6 6 6个MOO
。
【分析】
我们可以将任意字母映射成另一种字母,但是不能映射成自己本身,因此所有ABB
型且不为MOO
的字符串均可映射成MOO
。
枚举以每个点为起点,然后枚举向八个方向延伸所能构造出的长度为 3 3 3的字符串,如果构造出的字符串 s s s形如ABB
,且字符串的第一个字母不为M
,后两个字母不为O
,那么就将字符串 s s 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;
}
版权声明
本文为[柃歌]所创,转载请带上原文链接,感谢
https://blog.csdn.net/m0_51755720/article/details/124351977
边栏推荐
猜你喜欢
MIT: label every pixel in the world with unsupervised! Humans: no more 800 hours for an hour of video
Use of SVN:
CUMCM 2021-B:乙醇偶合制備C4烯烴(2)
系统编程之高级文件IO(十三)——IO多路复用-select
Structure of C language (Advanced)
Database management software sqlpro for SQLite for Mac 2022.30
redis优化系列(二)Redis主从原理、主从常用配置
初探 Lambda Powertools TypeScript
Get things technology network optimization - CDN resource request Optimization Practice
分享两个实用的shell脚本
随机推荐
About the three commonly used auxiliary classes of JUC
MySQL sorting feature details
Visualization Road (11) detailed explanation of Matplotlib color
remote: Support for password authentication was removed on August 13, 2021.
Cumcm 2021 - B: préparation d'oléfines C4 par couplage éthanol (2)
ConstraintLayout布局
mysql插入datetime类型字段不加单引号插入不成功
JDBC – PreparedStatement – 如何设置 Null 值?
学习 Go 语言 0x05:《Go 语言之旅》中映射(map)的练习题代码
How to quickly query 10 million pieces of data in MySQL
26. 删除有序数组中的重复项
MySQL interview questions explain how to set hash index
qt5.8 64 位静态库中想使用sqlite但静态库没有编译支持库的方法
MBA - day5 mathématiques - Questions d'application - Questions d'ingénierie
Google Earth Engine(GEE)——将原始影像进行升尺度计算(以海南市为例)
语雀文档编辑器将开源:始于但不止于Markdown
Upgrade the functions available for cpolar intranet penetration
oh-my-lotto
CUMCM 2021-B:乙醇偶合制备C4烯烃(2)
MIT: label every pixel in the world with unsupervised! Humans: no more 800 hours for an hour of video