矩阵

题目

给定一个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

输入样例:

3 3 2 2
111
000
111
3
11
00
11
11
00
11

输出样例:

1
0
1

分析

  • 这道题目思路简短,就是求出一个二维哈希前缀和,然后将a*b的全部hash值存进set容器里面去,然后每输入一个就求他的二维hash值,判断他在不在set里面即可。

代码

#include <iostream>
#include <algorithm>
#include <unordered_set>
using namespace std;
typedef unsigned long long ULL;
const int N=1e3+5,M=N*N,seed=131;

ULL h[N][N],p[N*N];
char str[N];

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

int main()
{
    int n,m,a,b;
    cin>>n>>m>>a>>b;
    p[0]=1;
    for(int i=1;i<=n*n;i++) p[i]=p[i-1]*seed;
    for(int i=1;i<=n;i++){
        scanf("%s",str+1);
        for(int j=1;j<=n;j++){ // 预处理每行的hash值 
            h[i][j]=h[i][j-1]*seed+str[j]-'0';
        }
    }

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

    int t;
    cin>>t;
    while(t--){
        ULL sum=0;
        for(int i=1;i<=a;i++){
            scanf("%s",str+1);
            for(int j=1;j<=b;j++){
                sum=sum*seed+str[j]-'0';
            }
        }
        if(s.count(sum)){
            cout<<"1"<<endl;
        }else{
            cout<<"0"<<endl;
        }
    } 
    return 0;
}  

   转载规则


《矩阵》 蒋曾辉 采用 知识共享署名 4.0 国际许可协议 进行许可。
  目录