刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

花坛

题目描述:

小明有一张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 #include using namespace std;int countSquares(int N, int M, vector>& grid) int count = 0;for (int i = 1; i <= N; i++) {for (int j = 1; j <= M; j++) {int same = 1;for (int x = i; x >= 1; x--) {for (int y = j; y >= 1; y--) {if (grid[x-1][y-1] != grid[i-1][j-1]) {same = 0;break;}}if (same == 0) break;}if (same == 1) {int width = i - 1;for (int k = j; k <= M; k++) {if (grid[width][k-1] != grid[i-1][j-1]) {break;}}int height = k - j;if (width >= 2 && height >= 2) {count++;}}}}return count;int main() int N, M;cin >> N >> M;vector> grid(N, vector(M));for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {cin >> grid[i][j];}}cout << countSquares(N, M, grid);return 0;```

解析:

【喵呜刷题小喵解析】:
本题要求统计一个N*M的方格纸中,需要涂抹颜料正方形矩阵的个数。每个小方格中都有a、b、c三种不同的花朵,涂色的花朵区域必须是一个正方形矩阵,最小为一个2*2的正方形矩阵,正方形矩阵中的花朵必须是同一种花朵。

我们可以使用暴力枚举的方法来解决这个问题。对于每个可能的正方形矩阵,我们检查它的四个顶点是否都是同一种花朵,如果是,则检查它的宽度和高度是否都大于等于2,如果是,则计数器加1。

具体实现时,我们可以使用两个嵌套的循环来枚举所有可能的正方形矩阵,对于每个矩阵,我们检查它的四个顶点是否都是同一种花朵,如果是,则继续检查它的宽度和高度是否都大于等于2,如果是,则计数器加1。

时间复杂度为O(N^2*M^2),空间复杂度为O(N*M)。虽然这个算法的时间复杂度较高,但是对于本题来说,由于N和M的取值范围较小,所以该算法可以在较短时间内得出正确答案。
创作类型:
原创

本文链接:花坛 题目描述: 小明有一张N*M(2≤N≤30,2≤M≤30)的方格纸,且每个小方格都是正方形,纸

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share