学步园

#include <iostream><br /> #include <cstring><br /> #include <cstdio><br /> #include <map><br /> #include <string><br /> using namespace std;<br /> struct TNode<br /> {<br /> int num;<br /> TNode * next[26];<br /> TNode()<br /> {<br /> num=0;<br /> memset(next,0,sizeof(next));<br /> }<br /> };<br /> int count[10]={1,3,3,3,3,3,4,3,4};<br /> char aset[10][4]={{'-'},{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};<br /> TNode * root =NULL;<br /> map<string,int>mq;<br /> void insert(char * s,int count)<br /> {<br /> int l = strlen(s);<br /> TNode * p = root;<br /> int i = 0;<br /> for(i=0;i<l;i++)<br /> {<br /> if(p->next[s[i]-'a']==NULL)<br /> {<br /> p->next[s[i]-'a'] = new TNode;<br /> p->next[s[i]-'a']->num = count;<br /> }<br /> else<br /> {<br /> p->next[s[i]-'a']->num+=count ;<br /> }<br /> p=p->next[s[i]-'a'];<br /> }<br /> }<br /> int find(char *s,int k)<br /> {<br /> int l = strlen(s);<br /> TNode * p =root;<br /> int i =0;<br /> for(i=0;i<l;i++)<br /> {<br /> if(p->next[s[i]-'a']==NULL)<br /> return 0;<br /> else<br /> {<br /> if(i==k-1)<br /> return p->next[s[i]-'a']->num;<br /> p = p->next[s[i]-'a'];<br /> }<br /> }<br /> return 0;<br /> }<br /> char buf[110];<br /> char max_buf[110];<br /> int max_f=0;<br /> bool check(char *s,int l)<br /> {<br /> string str(s,l+1);<br /> //cout<<str<<endl;<br /> map<string,int>::iterator it = mq.find(str);<br /> if(it == mq.end())<br /> return true;<br /> if(it->second == 0)<br /> return false;<br /> else<br /> return true;<br /> }<br /> void dfs(char *s,int l,int k)<br /> {<br /> if(k == l+1)<br /> {<br /> int tmp = find(buf,k);<br /> string s(buf,k);<br /> //cout<<s<<endl;<br /> if(tmp!=0)<br /> {<br /> pair<string ,int>pa(s,1);<br /> mq.insert(pa);<br /> }<br /> else<br /> {<br /> pair<string,int>pa(s,0);<br /> mq.insert(pa);<br /> }<br /> if(tmp > max_f)<br /> {<br /> max_f = tmp;<br /> memset(max_buf,0,sizeof(max_buf));<br /> memcpy(max_buf,buf,k);<br /> }<br /> return;<br /> }<br /> int i =0;<br /> for(i=0;i<count[s[k]-'1'];i++)<br /> {<br /> buf[k]=aset[s[k]-'1'][i];<br /> if(check(buf,k))<br /> dfs(s,l,k+1);<br /> }<br /> }<br /> void del(TNode * p)<br /> {<br /> int i = 0;<br /> for(i=0;i<26;i++)<br /> {<br /> if(p->next[i])<br /> del(p->next[i]);<br /> }<br /> delete p;<br /> }<br /> int main()<br /> {<br /> int t;<br /> scanf("%d",&t);<br /> int c=1;<br /> while(c<=t)<br /> {<br /> root = new TNode;<br /> mq.clear();<br /> printf("Scenario #%d:/n",c);<br /> int n,m;<br /> scanf("%d",&n);<br /> char word[110];<br /> int k=0;<br /> memset(word,0,sizeof(word));<br /> int i = 0;<br /> for(i=0;i<n;i++)<br /> {<br /> scanf("%s %d",word,&k);<br /> insert(word,k);<br /> }<br /> scanf("%d",&m);<br /> char dbuf[110];<br /> memset(dbuf,0,sizeof(dbuf));<br /> for(i=0;i<m;i++)<br /> {<br /> scanf("%s",dbuf);<br /> int l = strlen(dbuf);<br /> int j = 0;<br /> if(l==1)<br /> {<br /> }<br /> else<br /> {<br /> for(j=0;j<l-1;j++)<br /> {<br /> dfs(dbuf,j,0);<br /> if(max_f >0)<br /> {<br /> printf("%s/n",max_buf);<br /> }<br /> else<br /> {<br /> printf("MANUALLY/n");<br /> }<br /> max_f=0;<br /> memset(buf,0,sizeof(buf));<br /> }<br /> }<br /> printf("/n");<br /> memset(dbuf,0,sizeof(dbuf));<br /> }<br /> printf("/n");<br /> c++;<br /> del(root);<br /> }<br /> }