poj 1056 IMMEDIATE DECODABILITY

Description Input Output Sample Input Sample Output

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;

const int sonnum = 2, base = '0';
struct Trie 
{
  int num; bool terminal;
 Trie *son[sonnum];
};
Trie *NewTrie()
{
  Trie *temp = new Trie;
  temp->num = 1; temp->terminal = false;
  for (int i = 0; i < sonnum; ++i) temp->son[i] = NULL;
  return temp; 
}
bool Insert(Trie *pnt, char *s, int len)
{
  Trie *temp = pnt;
  bool mrk = true;
  for (int i = 0; i < len; ++i)
  {
    if (temp->son[s[i]-base] == NULL) temp->son[s[i]-base] = NewTrie();
    else 
    {
      temp->son[s[i]-base]->num++;
      if (temp->son[s[i]-base]->terminal == true)
        mrk = false;
    }
    temp = temp->son[s[i]-base];
  }
  temp->terminal = true;
  return mrk;
}

int main(void)
{
  Trie *tree;
  char a[20]; int cnt = 1;
#ifndef ONLINE_JUDGE
  freopen("poj2056.in", "r", stdin);
#endif
  while (~scanf("%s", a))
  {
    tree = NewTrie();
    bool flag = true;
    Insert(tree, a, strlen(a));
  while (~scanf("%s", a))
    {
      if (a[0] == '9') break;
      if (false == Insert(tree, a, strlen(a)))
        flag = false;
    }
//    if (a[0] == '9') continue;
    if (flag == false) printf("Set %d is not immediately decodable\n", cnt);
    else printf("Set %d is immediately decodable\n", cnt);
    cnt++;
}

  return 0;
}

又练习了一遍字典树，标记即可没有什么技术含量，代码还可以优化，习惯这么写了……虽然有点儿麻烦，至少是对的。