首页 > ACM题库 > HDU-杭电 > hdu 2456 Constellations[解题报告]hoj
2014
01-26

hdu 2456 Constellations[解题报告]hoj

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