题意:给定一个01矩阵。T个询问,每次询问大矩阵中是否存在这个特定的小矩阵。

 /*
64位的位运算!!!
题意:
给定一个01矩阵。T个询问,每次询问大矩阵中是否存在这个特定的小矩阵。
(64位记录状态!!!)
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<math.h>
using namespace std;
typedef long long int64;
//typedef __int64 int64;
typedef pair<int64,int64> PII;
#define MP(a,b) make_pair((a),(b))
const int maxn = ;
const int maxm = ;
const int inf = 0x7fffffff;
const double pi=acos(-1.0);
const double eps = 1e-; char mat[ maxn ][ maxn ];
char tmp[ maxm ][ maxm ];
int64 A[ maxn ][ maxn ];
int64 AA[ maxm ];
int64 sum[ maxn ][ maxn ]; void init( int n,int m,int p,int q ){
for( int i=;i<=m;i++ )
sum[][i] = ;
for( int i=;i<=n;i++ )
sum[i][] = ;
for( int i=;i<=n;i++ ){
for( int j=;j<=m;j++ ){
sum[ i ][ j ] = sum[i][j-]+sum[i-][j]-sum[i-][j-];
if( mat[i][j]=='*' )
sum[i][j] ++;
}
}
memset( A,,sizeof( A ) );
for( int i=;i<=n;i++ ){
for( int j=;j<=q;j++ ){
if( mat[i][j]=='*' )
A[i][q] |= ((1LL)<<(j-));
}
}
for( int i=;i<=n;i++ ){
for( int j=q+;j<=m;j++ ){
if( mat[i][j-q]=='*' ) A[i][j] = A[i][j-]-(1LL);
else A[i][j] = A[i][j-];
A[i][j] = A[i][j]>>(1LL);
if( mat[i][j]=='*' )
A[i][j] |= ((1LL)<<(q-));
}
}
} void GetBinary( int p,int q ){
for( int i=;i<=p;i++ ){
AA[ i ] = ;
for( int j=;j<=q;j++ ){
if( tmp[i][j]=='*' )
AA[ i ] |= ((1LL)<<(j-));
}
}
} int Judge( int n,int m,int p,int q,int64 cnt ){
for( int i=;i+p-<=n;i++ ){
if( sum[n][m]-sum[i-][m]<cnt ) break;
for( int j=q;j<=m;j++ ){
bool f = true;
for( int k=;k<=p;k++ ){
if( AA[k]!=A[i+k-][j] ){
f = false;
break;
}
}
if( f==true ) return ;
}
}
return ;
} int main(){
int n,m,t,p,q;
int Case = ;
while( scanf("%d%d%d%d%d",&n,&m,&t,&p,&q)== ){
if( n+m+t+p+q== ) break;
for( int i=;i<=n;i++ ){
scanf("%s",mat[i]+);
}
init( n,m,p,q );
int ans = ;
while( t-- ){
int64 cnt = ;
for( int i=;i<=p;i++ ){
scanf("%s",tmp[i]+);
for( int j=;j<=q;j++ ){
if( tmp[i][j]=='*' )
cnt++;
}
}
GetBinary( p,q );
ans += Judge( n,m,p,q,cnt );
}
printf("Case %d: ",Case++);
printf("%d\n",ans);
}
return ;
}

最新文章

  1. C++实例讲解Binder通信
  2. Spring-AOP实践 - 统计访问时间
  3. sujection重构
  4. [No000032]程序员的年龄天花板
  5. BZOJ1025: [SCOI2009]游戏
  6. sb 讲解 (!(~+[])+{})[--[~+&quot;&quot;][+[]]*[~+[]] + ~~!+[]]+({}+[])[[~!+[]]*~+[]]
  7. Android Sutido 编译速度优化
  8. NOPI读取EXCEL
  9. C++ lambda 表达式传递的变量默认不可变
  10. maven profile切换正式环境和测试环境
  11. How to setup a DL4J project with eclipse
  12. C语言第二次博客作业
  13. 《Java》第三周学习总结 20175301
  14. Java实现大数乘法运算
  15. linux无法联网使用yum提示cannot find a valid baseurl for repobase7x86_64
  16. 关于pycharm有时候提取不了form表单POST提交的数据
  17. centos7/rhel7安装较高版本ruby2.2/2.3/2.4+
  18. 向dnsrecord.txt 中添加 配置
  19. 服务网关zuul之六:Zuul高可用
  20. linux下部署jdk+Tomcat

热门文章

  1. Eclipse插件checkstyle 代码风格的检查
  2. Cocos移植到Android-Android.mk编译文件
  3. presentViewController: 如何不覆盖原先的 viewController界面
  4. iOS开发——开发者官网注册新设备
  5. Sql Server 维护计划 备份覆盖
  6. JavaScript学习笔记(13)——BOM
  7. 8个应该去逛逛JQuery的学习网站
  8. 静态的html页面想要设置使用浏览器缓存
  9. Catalyst揭秘 Day7 SQL转为RDD的具体实现
  10. 支持异步通知的globalfifo平台设备驱动程序及其测试代码