Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
branch: master
Fetching contributors…

Octocat-spinner-32-eaf2f5

Cannot retrieve contributors at this time

executable file 132 lines (116 sloc) 2.842 kb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131
/*
* =====================================================================================
*
* Filename: orion.cpp
*
* Description: POJ 3690. Constellation
*
* Version: 1.0
* Created: 07/03/2009 10:56:07 AM
* Revision: none
* Compiler: gcc
*
* Author: Ming Chen (chm), mingchen@cse.buaa.edu.cn
* Company: BUAA.edu
*
* =====================================================================================
*/


#include <iostream>
#include <cstring>

using namespace std;

const int MAXN = 1001;
const int MAXM = 126;
const int MAXP = 51;
const unsigned char masks[8] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80};

int num_found = 0;

class TNode {
    public:
bool found;
int count;
TNode *children[256];
TNode() : found(false), count(0) {
memset(children, sizeof(children), NULL);
};
~TNode() {
for (int i=0; i<256; ++i) {
if ( children[i] != NULL ) {
delete children[i];
children[i] = NULL;
}
}
};
};

TNode * insert(TNode *pnode, unsigned char *str, int n)
{
    if ( n == 0 ) return pnode;
    if ( pnode->children[*str] == NULL )
pnode->children[*str] = new TNode();
    return insert(pnode->children[*str], str+1, n-1);
}

TNode* search(TNode *pnode, unsigned char *str, int n)
{
    if ( n == 0 ) return pnode;
    if ( pnode->children[*str] == NULL )
return NULL;
    return search(pnode->children[*str], str+1, n-1);
}

unsigned char getbyte(char *p, int n)
{
    unsigned char c = 0;
    int lim = n < 8 ? n : 8;
    for (int i=0; *p != '\0' && i < lim; ++i) {
if ( *p++ == '*' ) c |= masks[i];
    }
    return c;
}

int main()
{
    TNode *root, *pnode;
    int N, M, T, P, Q, Qb, caseNo=1;
    unsigned char line[MAXM];
    char constellation[MAXP][MAXP];
    char sky[MAXN][MAXN];

    while ( cin >> N >> M >> T >> P >> Q ) {
num_found = 0;
if ( N == 0 ) break;
for (int n=0; n<N; ++n) {
do {
cin.getline(sky[n], M+1);
} while ( sky[n][0] == '\0' );
}

// build trie
Qb = (Q+8-1)/8;
root = new TNode();
for (int n=0; n<=N-P; ++n) {
for (int m=0; m<=M-Q; ++m) {
pnode = root;
for (int p=0; p<P; ++p) {
for (int q=0; q<Q; q+=8) {
line[q>>3] = getbyte(sky[n+p]+m+q, Q-q);
}
pnode = insert(pnode, line, Qb);
}
}
}

// read candidates and search
for (int t=1; t<=T; ++t) {
pnode = root;
for (int p=0; p<P; ++p) {
do {
cin.getline(constellation[p], Q+1);
} while ( constellation[p][0] == '\0' );
}
for (int p=0; p<P; ++p) {
for (int q=0; q<Q; q+=8) {
line[q>>3] = getbyte(constellation[p]+q, Q-q);
}
pnode = search(pnode, line, Qb);
if ( pnode == NULL ) break;
}
if ( pnode != NULL ) ++num_found;
}

cout << "Case " << caseNo++ << ": " << num_found << endl;
delete root;
    }

    return 0;
}
Something went wrong with that request. Please try again.