ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1227 77377

問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1227


・概要
携帯電話で文章を打つ問題です。
文字を打つ内容が数字で与えられて、そのとき表示できる文章を全通り出力する感じです。


・解法
DFSで解くことができます。

ボタンとアルファベットの対応表を元に、与えられる単語を数字に変換しておくと比較が楽にできると思います。


ソースコード

#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<sstream>
#include<cstdio>
#include<cstdlib>
using namespace std;

#define rep(i,n) for(int i = 0 ; i < (int)(n) ; i++)
#define f first
#define s second
#define mp make_pair
typedef pair<string, string> P;

int n;
char alphaList[26]={'2','2','2',
		    '3','3','3',
		    '4','4','4',
		    '5','5','5',
		    '6','6','6',
		    '7','7','7','7',
		    '8','8','8',
		    '9','9','9','9'};
string key;
P word[100];
vector<string> ans;

void solve(int pos, string num, string str){
   if(pos==key.size()){
      if(num.size()!=0)return;
      ans.push_back(str + ".");
   }
   else{
      num += key[pos++];
      
      for(int i = 0 ; i < n ; i++){
	 if(num==word[i].s){
	    string tmp = "";
	    if(str.size()==0)tmp = word[i].f;
	    else tmp = str + " " + word[i].f;
	    solve(pos, "", tmp);
	 }
      }
      solve(pos, num, str);
   }
}

int main(){
   while(cin >> n){
      if(n==0)break;
  
      for(int i = 0 ; i < n ; i++){
	 string str;
	 cin >> str;
	 string num = "";
	 for(int j = 0 ; j < str.size() ; j++){
	    num += alphaList[(int)str[j]-'a'];
	 }
	 word[i] = mp(str,num);
      }
      
      cin >> key;

      ans.clear();
      solve(0,"","");

      for(int i = 0 ; i < ans.size() ; i++){
	 cout << ans[i] << endl;
      }
      cout << "--" << endl;
   }
   return 0;
}