A33799. 花坛
填空题
困难
知识点
题目描述
花坛
题目描述
小明有一张N*M（2≤N≤30，2≤M≤30）的方格纸，且每个小方格都是正方形，纸上的每个小方格中都画了一个花朵，共有a、b、c三种不同的花朵。为了美观现按照以下要求为花朵涂色。
要求：
1）涂色的花朵区域必须是一个正方形矩阵，最小为一个2*2的正方形矩阵；
2）正方形矩阵中的花朵必须是同一种花朵；
3）只要正方形矩阵四个顶点不重合就算作不同的正方形矩阵（有部分区域重叠或者大正方形矩阵包含小正方形矩阵，按不同的正方形矩阵计算）。
已知方格纸的行数N（2≤N≤30）和列数M（2≤M≤30），及每个小正方形方格中花朵的种类，请帮助小明计算出，按要求有多少个正方形矩阵需要涂色。
例如：N=4，D = 5，矩阵如下图：
其中有3个正方形矩阵需要涂抹颜料（蓝色框区域和绿色区域的矩阵部分重叠按2个计算）。
输入描述
第一行输入两个正整数N(2≤N≤30)和M(2≤M≤30)，N表示矩阵方格的行数，M表示矩阵方格的列数，两个正整数之间以一个空格隔开
第二行开始输入N行，每行M个字符(字符只包含a、b、c)，字符之间以一个空格隔开
输出描述
输出一个整数，表示N*M的矩阵方格纸中，需要涂抹颜料正方形矩阵的个数
样例输入
4 5
b b c b a
b b a c b
c b a a a
a b a a a
样例输出
3
参考答案
#include<iostream>
using namespace std;
const int N = 30;
char a[N + 1][N + 1];
int main() {
int n, m, cnt = 0;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
for (int e = 2; e <= min(m, n); e++) {
for (int i = 0; i <= n - e; i++) {
for (int j = 0; j <= m - e; j++) {
bool f = true;
for (int x = 0; x < e; x++) {
for (int y = 0; y < e; y++) {
if (a[i][j] != a[i + x][j + y]) {
f = false;
break;
}
}
if (!f) {
break;
}
}
if (f) {
cnt++;
}
}
}
}
cout << cnt;
return 0;
}
上一题
下一题