2014
01-26

# Constellations

The starry sky in the summer night is one of the most beautiful things on this planet. People imagine that some groups of stars in the sky form so-called constellations. Formally a constellation is a group of stars that are connected together to form a figure or picture. Some well-known constellations contain striking and familiar patterns of bright stars. Examples are Orion (containing a figure of a hunter), Leo (containing bright stars outlining the form of a lion), Scorpius (a scorpion), and Crux (a cross).

In this problem, you are to find occurrences of given constellations in a starry sky. For the sake of simplicity, the starry sky is given as a N × M matrix, each cell of which is a ‘*’ or ’0′ indicating a star in the corresponding position or no star, respectively. Several constellations are given as a group of T P × Q matrices. You are to report how many constellations appear in the starry sky.

Note that a constellation appears in the sky if and only the corresponding P × Q matrix exactly matches some P × Q sub-matrix in the N × M matrix.

The input consists of multiple test cases. Each test case starts with a line containing five integers N, M, T, P and Q(1 ≤ N, M ≤ 1000, 1 ≤ T ≤ 100, 1 ≤ P, Q ≤ 50).
The following N lines describe the N × M matrix, each of which contains M characters ‘*’ or ’0′.
The last part of the test case describe T constellations, each of which takes P lines in the same format as the matrix describing the sky. There is a blank line preceding each constellation.
The last test case is followed by a line containing five zeros.

The input consists of multiple test cases. Each test case starts with a line containing five integers N, M, T, P and Q(1 ≤ N, M ≤ 1000, 1 ≤ T ≤ 100, 1 ≤ P, Q ≤ 50).
The following N lines describe the N × M matrix, each of which contains M characters ‘*’ or ’0′.
The last part of the test case describe T constellations, each of which takes P lines in the same format as the matrix describing the sky. There is a blank line preceding each constellation.
The last test case is followed by a line containing five zeros.

3 3 2 2 2
*00
0**
*00

**
00

*0
**
3 3 2 2 2
*00
0**
*00

**
00

*0
0*
0 0 0 0 0

Case 1: 1
Case 2: 2

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<string>

using namespace std;

const int maxn = 1010;
char s[maxn][maxn];

struct Node
{
int next[2];
int count;
void init()
{
next[0] = next[1] = -1;
count =0;
}
}node[50*50*110];
int cnt;

int newNode()
{
node[cnt].init();
return cnt++;
}

char code(char c)
{
if(c=='*')  return 0;
return 1;
}

void insert(char *s)
{
int p=0;
while(*s)
{
int i = code(*s);
s++;
if(node[p].next[i]==-1) node[p].next[i] = newNode();
p = node[p].next[i];
}

node[p].count++;
// printf("%d -> %d\n",p,node[p].count);
}

char  t[50*55];

int main()
{
// freopen("in","r",stdin);
int cases = 1;
int n,m,T,p,q;
while(scanf("%d%d%d%d%d",&n,&m,&T,&p,&q),n||m||T||p||q)
{
int i,j,k,ii,jj;
for(i=0;i<n;i++)
scanf("%s",s[i]);

node[0].init();
cnt = 1;
for(i=0;i<T;i++)
{
for(ii=0;ii<p;ii++)
scanf("%s",t+ii*q);
insert(t);
// cout<<t<<endl;
}

int ans =0;
for(i=0;i+p<=n;i++)
for(j=0;j+q<=m;j++)
{
int pp=0;
for(ii=0;ii<p&&pp!=-1;ii++)
for(jj=0;jj<q;jj++)
{
int c = code(s[i+ii][j+jj]);
pp=node[pp].next[c];
if(pp==-1)   break;
}

if(pp==-1)   continue;
ans += node[pp].count;
// cout<<"pp="<<pp<<"ans="<<ans<<endl;
// if(ans>=T)  break;
node[pp].count = 0;
}

printf("Case %d: %d\n",cases++,ans);
}
return 0;
}

1. int half(int *array,int len,int key)
{
int l=0,r=len;
while(l<r)
{
int m=(l+r)>>1;
if(key>array )l=m+1;
else if(key<array )r=m;
else return m;
}
return -1;
}
这种就能避免一些Bug
l,m,r
左边是l,m;右边就是m+1,r;

2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks