ABC430B 子网格计数
大约 2 分钟数据结构
ABC430B 子网格计数
【算法标签】 数据结构/哈希表/枚举
【语法标签】 :二维数组、map/set、string、for循环
在 的网格中,枚举所有 的连续子区域,统计其中不同的颜色图案有多少种。
二、算法思路
暴力枚举所有可能的子区域左上角坐标 ,其中 。
对于每个子区域,按行优先顺序依次拼接每个格子字符,形成一个唯一的字符串表示该图案。
将字符串存入哈希集合(去重)。
最后输出集合的大小。
使用
map映射也可以,本质上思路一致。
三、流程图 和参考代码
输入 N, M 和网格字符矩阵
创建哈希集合 set<string>
for i = 0 to N-M:
for j = 0 to N-M:
初始化空串 pattern
for x = i to i+M-1:
for y = j to j+M-1:
pattern += grid[x][y]
将 pattern 插入集合
输出集合大小参考代码:
#include <bits/stdc++.h>
using namespace std;
char a[15][15];
int main(){
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
cin >> a[i][j];
}
}
map<string, int> mp;
// 开始选择
for(int i = 1; i <= n - m + 1; i++){
for (int j = 1; j <= n - m + 1; j++){
// 现在开始从起点 a[i][j] 开始的 子矩阵
string s;
for(int rol = i; rol <= i + m - 1; rol++){
for(int col = j; col <= j + m - 1; col++){
s += a[rol][col];
}
}
// 将拼接的字符串放到 map中
mp[s]++;
}
}
cout << mp.size();
return 0;
}四、复杂度分析
- ,最多有$ (N-M+1)² ≤ 100 $个子区域。
- 每个子区域遍历 个字符,字符串最大长度 。
- 总操作次数约 ,非常快。
五、实现要点
- 网格输入:每行读入一个长度为 的字符串(不包含空格)。
- 集合推荐使用
unordered_set(需要头文件和std::string)。 - 字符串拼接时注意顺序:先行后列,保证相同图案得到相同字符串。
知识点强化记忆:
set:有序、不重复
unordered_set:无序、不重复、最快
multiset:有序、可重复