| Problem description |
|
Samuel W. E. R. Craft is an artist with a growing reputation. Unfortunately, the paintings he sells do not provide him enough money for his daily expenses plus the new supplies he needs. He had a brilliant idea yesterday when he ran out of blank canvas:
"Why don’t I create a gigantic new painting, made of all the unsellable paintings I have, stitched together?". After a full day of work, his masterpiece was complete. |
| Input |
|
|
| Output |
|
A single integer representing the number of possible locations where his painting might be. |
| Sample Input |
4 4 10 10 oxxo xoox xoox oxxo xxxxxxoxxo oxxoooxoox xooxxxxoox xooxxxoxxo oxxoxxxxxx ooooxxxxxx xxxoxxoxxo oooxooxoox oooxooxoox xxxoxxoxxo |
| Sample Output |
4 |
| Problem Source |
|
HNU Contest
题意： 给出两个图，问大图中包含几个小图
思路： 用数字保存是一种方法，本以为超类型肯定不行的，没有想到居然也能AC，不知道是数据水还是数据保存方面的一些玄机？
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>
using namespace std;
#define ls 2*i
#define rs 2*i+1
#define UP(i,x,y) for(i=x;i<=y;i++)
#define DOWN(i,x,y) for(i=x;i>=y;i--)
#define MEM(a,x) memset(a,x,sizeof(a))
#define W(a) while(a)
#define gcd(a,b) __gcd(a,b)
#define LL long long
#define ULL unsigned long long
#define N 2005
#define INF 0x3f3f3f3f
#define EXP 1e-8
#define rank rank1
const int mod = 1000000007;
int h1,h2,w1,w2,ans;
char s1[N][N],s2[N][N];
const ULL t1 = 7;
const ULL t2 = 11;
ULL sum,a[N][N],b[N][N];
void solve()//把大图用数字表示的同时找出与小图相等的位置
{
int i,j,k;
ULL x=1;
for(i = 0; i<w1; i++) x*=t1;
for(i = 0; i<h2; i++)
{
ULL s = 0;
for(j = 0; j<w1; j++) s = s*t1+s2[i][j];
a[i][w1-1] = s;
for(j = w1; j<w2; j++)
a[i][j] = a[i][j-1]*t1-s2[i][j-w1]*x+s2[i][j];
}
x = 1;
for(i = 0; i<h1; i++) x*=t2;
for(i = w1-1; i<w2; i++)
{
ULL s = 0;
for(j = 0; j<h1; j++) s = s*t2+a[j][i];
b[h1-1][i] = s;
if(s==sum) ans++;
for(j = h1; j<h2; j++)
{
b[j][i] = b[j-1][i]*t2-a[j-h1][i]*x+a[j][i];
if(b[j][i]==sum) ans++;
}
}
}
int main()
{
int i,j,k;
while(~scanf("%d%d%d%d",&h1,&w1,&h2,&w2))
{
for(i = 0; i<h1; i++) scanf("%s",s1[i]);
for(i = 0; i<h2; i++) scanf("%s",s2[i]);
sum = 0;
for(i = 0; i<h1; i++)//把小图用数字表示
{
ULL s = 0;
for(j = 0; j<w1; j++)
{
s = s*t1+s1[i][j];
}
sum = sum*t2+s;
}
ans = 0;
solve();
printf("%d\n",ans);
}
return 0;
}
|
版权声明：本文为博主原创文章，未经博主允许不得转载。
原文：http://blog.csdn.net/libin56842/article/details/47403759
