1227 - 77377

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1227

問題

"2"なら"a","b","c"の3通りが考えられる。
辞書が与えられるのでその単語が使われるような文を全て出力する。という程度の問題。

解法

DFS。
辞書の文字は対応する数字にしてしまって、入力と等しいかどうか判定する。

ソース

int n;
string dic[100];
string s[100];
string input;

void dfs(int pos, string ans) {
  if (pos == input.size()) {
    cout << ans + "." << endl;
    return;
  }
  REP(i,n) {
    if (pos + dic[i].size() > input.size()) continue;
    if (dic[i] == input.substr(pos, dic[i].size())) {
      dfs(pos + dic[i].size(), ans + (pos?" ":"") + s[i]);
    }
  }
}

int main() {
  int button = 2, cnt = 0;
  map<char, int> mp;
  for (char c='a'; c<='z'; ++c) {
    mp[c] = button;
    cnt++;
    if (cnt == 4 || (button != 7 && button != 9) && cnt == 3) {
      cnt = 0;
      button++;
    }
  }
  while(cin >> n, n) {
    REP(i,n) {
      cin >> s[i];
      dic[i] = "";
      FOR(it, s[i]) {
        dic[i].push_back(mp[*it]+'0');
      }
    }
    cin >> input;
    dfs(0, "");
    cout << "--" << endl;
  }
}