当前位置:网站首页>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
边栏推荐
- 年度最尴尬的社死瞬间,是Siri给的
- The songbird document editor will be open source: starting with but not limited to markdown
- Oracle connectivity test gadget
- 学习 Go 语言 0x02:对切片 Slice 的理解
- Structure of C language (Advanced)
- Difference between pregnancy box and delivery box
- Usage of rename in cygwin
- qt5.8 64 位静态库中想使用sqlite但静态库没有编译支持库的方法
- Applet payment
- R-drop: a more powerful dropout regularization method
猜你喜欢
Mysql8.0安装指南
C#的学习笔记【八】SQL【一】
Promise details
一道有趣的阿里面试题
采用百度飞桨EasyDL完成指定目标识别
Google Earth engine (GEE) - scale up the original image (taking Hainan as an example)
VM set up static virtual machine
Typora operation skill description (I) md
R-drop: a more powerful dropout regularization method
CUMCM 2021-b: preparation of C4 olefins by ethanol coupling (2)
随机推荐
Microsoft Access database using PHP PDO ODBC sample
Visual common drawing (V) scatter diagram
Solutions to common problems in visualization (IX) background color
学习网站资料
学习 Go 语言 0x04:《Go 语言之旅》中切片的练习题代码
@valid,@Validated 的学习笔记
Excel·VBA数组冒泡排序函数
Usage Summary of datetime and timestamp in MySQL
laravel-admin表单验证
MySQL数据库事务transaction示例讲解教程
JDBC – PreparedStatement – 如何设置 Null 值?
26. Delete duplicates in ordered array
stylecloud ,wordcloud 库学习及使用例子
PlatoFarm推出正式版游戏经济模型的特点分析
Three web components (servlet, filter, listener)
Visual common drawing (III) area map
得物技术网络优化-CDN资源请求优化实践
Google Earth engine (GEE) - scale up the original image (taking Hainan as an example)
学习 Go 语言 0x01:从官网开始
Data analysis learning (I) data analysis and numpy Foundation