zoj1511.cpp

最近在acm.zju.edu.cn上通过的题目的代码

#include<iostream>
#include<string>
using namespace std;

struct trienode {
    trienode* ch[26];
    int key;

    trienode(int x=-1):key(x) {
        for(int i=0;i<26;i++)
            ch[i]=NULL;
    }

    void insert(const char* x,const int y) {
        if (*x) {
            if (ch[*x-'A']==NULL) {
                ch[*x-'A']=new trienode;
            }
            ch[*x-'A']->insert(x+1,y);
        } else {
            key=y;
        }
    }
} *root;

int l,c,w;
char sq[1010][1010],wl[1010][2010];
int ansx[1010],ansy[1010],ansd[1010];
bool first = true;

const int dx[]={-1,-1,0,1,1,1,0,-1};
const int dy[]={0,1,1,1,0,-1,-1,-1};

bool init() {
    if (EOF == scanf("%d%d%d",&l,&c,&w)) return false;
    if (first) first = false; else puts("");
    for(int i=0;i<l;i++)
        scanf("%s",sq[i]);
    for(int i=0;i<w;i++) {
        scanf("%s",wl[i]);
    }
    root=new trienode;
    for(int i=0;i<w;i++) {
        root->insert(wl[i],i);
    }
    return true;
}

bool inrange(int x,int y) {
    return 0<=x && x<l && 0<=y && y<c;
}

void calc() {
    memset(ansx,0xff,sizeof(ansx));
    memset(ansy,0xff,sizeof(ansy));
    memset(ansd,0xff,sizeof(ansd));
    for(int i=0;i<l;i++)
        for(int j=0;j<c;j++) {
            for(int k=0;k<8;k++) {
                int x=i,y=j;
                trienode* p=root;
                while (true) {
                    p=p->ch[sq[x][y]-'A'];
                    if (p==NULL) break;
                    if (p->key>=0)
                        if (ansd[p->key]<0) {
                            ansx[p->key]=i;
                            ansy[p->key]=j;
                            ansd[p->key]=k;
                        }
                    x+=dx[k];
                    y+=dy[k];
                    if (!inrange(x,y)) {
                        break;
                    }
                }
            }
        }
    for(int i=0;i<w;i++)
        printf("%d %d %c\n",ansx[i],ansy[i],ansd[i]+'A');
}

int main() {
    while (init()) calc();
}