/*
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 = 1005;
const int maxm = 55;
const int inf = 0x7fffffff;
const double pi=acos(-1.0);
const double eps = 1e-8;
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=0;i<=m;i++ )
sum[0][i] = 0;
for( int i=0;i<=n;i++ )
sum[i][0] = 0;
for( int i=1;i<=n;i++ ){
for( int j=1;j<=m;j++ ){
sum[ i ][ j ] = sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
if( mat[i][j]=='*' )
sum[i][j] ++;
}
}
memset( A,0,sizeof( A ) );
for( int i=1;i<=n;i++ ){
for( int j=1;j<=q;j++ ){
if( mat[i][j]=='*' )
A[i][q] |= ((1LL)<<(j-1));
}
}
for( int i=1;i<=n;i++ ){
for( int j=q+1;j<=m;j++ ){
if( mat[i][j-q]=='*' ) A[i][j] = A[i][j-1]-(1LL);
else A[i][j] = A[i][j-1];
A[i][j] = A[i][j]>>(1LL);
if( mat[i][j]=='*' )
A[i][j] |= ((1LL)<<(q-1));
}
}
}
void GetBinary( int p,int q ){
for( int i=1;i<=p;i++ ){
AA[ i ] = 0;
for( int j=1;j<=q;j++ ){
if( tmp[i][j]=='*' )
AA[ i ] |= ((1LL)<<(j-1));
}
}
}
int Judge( int n,int m,int p,int q,int64 cnt ){
for( int i=1;i+p-1<=n;i++ ){
if( sum[n][m]-sum[i-1][m]<cnt ) break;
for( int j=q;j<=m;j++ ){
bool f = true;
for( int k=1;k<=p;k++ ){
if( AA[k]!=A[i+k-1][j] ){
f = false;
break;
}
}
if( f==true ) return 1;
}
}
return 0;
}
int main(){
int n,m,t,p,q;
int Case = 1;
while( scanf("%d%d%d%d%d",&n,&m,&t,&p,&q)==5 ){
if( n+m+t+p+q==0 ) break;
for( int i=1;i<=n;i++ ){
scanf("%s",mat[i]+1);
}
init( n,m,p,q );
int ans = 0;
while( t-- ){
int64 cnt = 0;
for( int i=1;i<=p;i++ ){
scanf("%s",tmp[i]+1);
for( int j=1;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 0;
}
分享到:
相关推荐
2遍dp poj_3613解题报告 poj_3613解题报告
人们熟悉的四则运算表达式称为中缀表达式,例如(23+34*45/(5+6+7))。在程序设计语言中,可以利用堆栈的方法把中缀表达式转换成保值的后缀表达式(又称逆波兰表示法),并最终变为计算机可以直接执行的指令,得到...
poj 5346题,四则运算表达式求值的实现,用栈和队列实现中缀转后缀后计算,含解题报告与源码
自己写得大数浮点数幂运算(c++实现),系poj acm 的problem:1001的实现
这是一个状态压缩动态规划的题型。采用二进制移位等各种运算和dp的思想。
要大整数乘法的 数组形式实现 poj 大整数乘法法 代码
在poj上accepted的代码。对大整数进行了封装,能很方便地求而出1000位以内的整数的运算。
1.13 矢量运算求几何模板 35 1.14结构体表示几何图形 47 1.15四城部分几何模板 52 1.16 一些代码 54 1.16.1 最小圆覆盖_zju1450 54 1.16.2 直线旋转_两凸包的最短距离(poj3608) 58 1.16.3 扇形的重心 62 1.16.4 根据...
位运算 离散化 区间合并 单链表 双链表 栈 队列 单调栈 单调队列 KMP Tire 并查集 堆 哈希表 DFS BFS 快速幂 背包问题 区间DP 区间问题 绝对值不等式 DP课 寒假每日一题 基础班 提高班 POJ 大二 2019 新生赛 蓝桥杯...
实数精度 在实数运算中,经常需要判断实数x和实数y是否相等,而编程者往往把判断条件简单设成y-x是否等于0。但这样的做法可能会产生精度误差。避免精度误差的办法是设一个精度常量delta。若y-x的实数值与0之间的...
1.4.1 POJ的提交方法 1.4.2 GCJ的提交方法 1.5 以高效的算法为目标 1.5.1 什么是复杂度 1.5.2 关于运行时间 1.6 轻松热身 1.6.1 先从简单题开始 1.6.2 POJ的题目Ants 1.6.3 难度增加的抽签问题 阅读 第2章 初出茅庐...