画

GitHub跳转原题关系图返回列表

3×3 小矩阵只有 3^9 种形态，把每块压缩成三进制整数用 bool 数组标记，O(1) 去重计数。

OJ: roj

题目 ID: 20021

难度:入门

标签:哈希枚举

创建: 2026-08-29 00:09

更新: 2026-10-07 13:50

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

给定 n×mn\times m 的像素矩阵，n,mn,m 均为 33 的倍数，每格为 R/G/B 之一。把矩阵按行列各均分成 3×33\times 3 的小矩阵，去重后求不同小矩阵的数量。

输入第一行 n,mn,m，接下来 nn 行每行一个长度 mm 的 RGB 字符串；输出一个整数表示重复度。样例：3 3 的三行 RGB 输出 1；6 6 的四色块样例输出 3。100%100\% 数据 n,m≤3000n,m\le 3000。

思路

3x3 小矩阵只有 39=196833^9=19683 种形态，按行优先把每块压成三进制整数（R=0、G=1、B=2），用 bool seen[19683] 标记，首次出现就计入答案。

参考代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-28 23:40
 * update_at: 2026-08-28 23:40
 */
// main.cpp：把每个 3x3 小矩阵编码成一个 9 位三进制数（R=0, G=1, B=2），
// 用 bool seen[19683] 标记出现过的编码，统计不同小矩阵的数量。
// 复杂度 O(nm)：每个像素恰好被扫一次。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3005;      // n <= 3000
const int MAXCODE = 19683;  // 3^9：9 个格子每格取 R/G/B 之一，共 3^9 种小矩阵

int n, m;
string g[MAXN];      // 像素矩阵的每一行
bool seen[MAXCODE];  // seen[x] = true 表示编码为 x 的 3x3 小矩阵已出现过

// 把颜色字符映射成三进制位：R -> 0，G -> 1，B -> 2。
int color_id(char c) {
    if (c == 'R') return 0;
    if (c == 'G') return 1;
    return 2; // 'B'
}

// 提取左上角为 (x, y) 的 3x3 小矩阵，按行优先顺序拼成三进制数。
// 逐位 code = code * 3 + 当前颜色，编码唯一落在 0..19682。
int encode(int x, int y) {
    int code = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            code = code * 3 + color_id(g[x + i][y + j]);
        }
    }
    return code;
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> g[i];

    int ans = 0;
    // 横向 n/3 块、纵向 m/3 块；块 (bi, bj) 的左上角是 (bi*3, bj*3)。
    for (int bi = 0; bi < n / 3; bi++) {
        for (int bj = 0; bj < m / 3; bj++) {
            int code = encode(bi * 3, bj * 3);
            if (!seen[code]) {
                seen[code] = true;
                ans++;
            }
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}