1654.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1654 on 2006-01-19 at 03:51:38 */ 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <map>
using namespace std;

const int L_MAX = 64;
const int MAX = 80000;
const char letter[] = "ejnqrwxdsyftamcivbkulopghz";
const char digit[] = "01112223334455666777888999";
typedef vector<const char*> vs;

struct scmp {
	bool operator ()(const char* s1, const char* s2) const {
		return strcmp(s1, s2) < 0;
	}
};

class Word {
private:
	static char f[];
public:
	char spell[L_MAX], num[L_MAX];
	int l;
	static void init();
	void parse();
};
char Word::f[256] = "";
void Word::init() {
	int i;
	memset(f, 0, sizeof(f));
	for(i = 0; letter[i] != 0; i++) f[letter[i]-'a'+'A'] = f[letter[i]] = digit[i];
	for(i = 0; i < 10; i++) f[i+'0'] = i + '0';
}
void Word::parse() {
	int i;
	l = 0;
	for(i = 0; spell[i] != 0; i++) 
		if(f[spell[i]] != 0) num[l++] = f[spell[i]];
	num[l] = 0;
}

int cmp(const void*, const void*);
void print(const Word&, int);

map<const char*, vs, scmp> dict;
Word word[MAX];
int sl;
bool reach[L_MAX];

vector<const char*>::iterator is[L_MAX];
int it;
char re[800][L_MAX];

int main()
{
	Word phone;
	int n, m, T, t;
	int i, j, k, l;

	Word::init();
	scanf("%d", &T);
	for(t = 1; t <= T; t++) {
		scanf("%d\n", &n);
		for(i = 0; i < n; i++) {
			gets(word[i].spell);
			word[i].parse();
		}
		dict.clear();
		for(i = 0; i < n; i++) dict[word[i].num].push_back(word[i].spell);
		printf("Scenario #%d:\n", t);
		scanf("%d\n", &m);
		for(k = 0; k < m; k++) {
			gets(phone.spell);
			phone.parse();
			memset(reach, false, sizeof(reach));
			reach[phone.l] = true;
			for(i = phone.l-1; i >= 0; i--) {
				for(j = i-1; j >= 0; j--) {
					char str[L_MAX] = {0};
					for(l = j; l <= i; l++) str[l-j] = phone.num[l];
					if(!reach[j] && reach[i+1] && dict.count(str) != 0) 
						reach[j] = true;
				}
			}
			if(!reach[0]) printf("%s cannot be encoded.\n", phone.spell);
			else {
				it = sl = 0;
				print(phone, 0);
				qsort(re, sl, sizeof(re[0]), cmp);
				for(i = 0; i < sl; i++) printf("%s:%s\n", phone.spell, re[i]);
			}
		}
		putchar('\n');
	}
	
	return 0;
}

int cmp(const void* a, const void* b)
{
	char *x = (char*)a, *y = (char*)b;
	return strcmp(x, y);
}
void print(const Word& w, int begin)
{
	int i, j;
	if(begin == w.l) {
		char *x = re[sl++];
		for(i = 0; i < it; i++) {
			sprintf(x, " %s", *is[i]);
			x += strlen(*is[i]) + 1;
		}
	} else {
		for(i = begin+1; i <= w.l; i++)
			if(reach[i]) {
				char str[L_MAX] = { 0 };
				for(j = begin; j < i; j++) str[j-begin] = w.num[j];
				if(dict.count(str) != 0) {
					vs &v = dict.find(str)->second;
					for(is[it] = v.begin(); is[it] != v.end(); is[it]++) {
						it++; print(w, i); it--;
					}
				}
			}
	}
}