AcWing-156-矩阵

2021-04-27 · 88次阅读 · 原创 · 数据结构与算法

#哈希 #算法竞赛 #题解

问题

给定一个 M 行 N 列的 01 矩阵（只包含数字 0 或 1 的矩阵），再执行 Q 次询问，每次询问给出一个 A 行 B 列的 01 矩阵，求该矩阵是否在原矩阵中出现过。

输入格式

第一行四个整数 M,N,A,B。

接下来一个 M 行 N 列的 01 矩阵，数字之间没有空格。

接下来一个整数 Q。

接下来 Q 个 A 行 B 列的 01 矩阵，数字之间没有空格。

输出格式

对于每个询问，输出 1 表示出现过，0 表示没有出现过。

数据范围

A≤100，M,N,B≤1000，Q≤1000

输入样例：

输出样例：

1
0
1

思路

字符串Hash

扫描原矩阵 m * n，将每个 a * b 子矩阵按照如下位置进行Hash，g[3][3]为第0未，g[3][2]为第一位，…g[1][1] 为第8位数字，hash完成后存入 set 集合去重，在每次询问的时候，将询问的每个 a * b 矩阵也按照下面方式进行Hash，Hash完成后去之前的set集合查找是否存在该结果，存在则输出 1，否则输出 0 。

题解

#include<iostream>
#include<cstdio>
#include<unordered_set>

using namespace std;
const int N = 1005, M = N * N, BASE = 131;
typedef unsigned long long ULL;
ULL h[N][N], p[M];
int m, n, a, b;
char str[N];

ULL get(ULL f[], int l, int r) {
    return f[r] - f[l - 1] * p[r - l + 1];
}

int main() {
    scanf("%d%d%d%d", &m, &n, &a, &b);
    p[0] = 1;
    for (int i = 1; i <= m * n; i++) p[i] = p[i - 1] * BASE;
    for (int i = 1; i <= m; i++) {
        scanf("%s", str + 1);
        for (int j = 1; j <= n; j++) h[i][j] = h[i][j - 1] * BASE + str[j] - '0';
    }

    unordered_set<ULL> S;
    for (int i = 1; i + b - 1 <= n; i++) {    //列
        ULL s = 0;
        int l = i, r = i + b - 1;
        for (int j = 1; j <= m; j++) {    //行
            s = s * p[b] + get(h[j], l, r);
            if (j > a) s -= get(h[j - a], l, r) * p[a * b];
            if (j >= a) S.insert(s);
        }
    }

    int k;
    scanf("%d", &k);
    while (k--) {
        ULL s = 0;
        for (int i = 0; i < a; i++) {
            scanf("%s", str);
            for (int j = 0; j < b; j++) s = s * BASE + str[j] - '0';
        }

        if (S.count(s)) puts("1");
        else puts("0");
    }

    return 0;
}

标题：	AcWing-156-矩阵
链接：	https://www.fightingok.cn/detail/85
更新：	2022-09-18 22:37:41
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可