HDOJ 2360 Word Ladder

Posted by twcai in ACM/ICPC on August 28, 2008

BFS+路径保存即可。枚举所有单词作为“第一阶”，找只差一个字母的单词扩展节点，记录该单词前驱，当扩展的单词和第一个单词完全不同时结束BFS。枚举N次，每次碰到比原有情况更短的“阶梯”，就把路径保存下来。题目要求多结果时按字典序输出，只要在读入单词后，对所有单词按字典序排序就可以啦。
有一个比较重要的优化就是对所有单词进行预处理，把只相差一个字母的一对单词和完全不同的一对单词记录下来(我用邻接矩阵保存)，然后在进行bfs。在枚举过程中，碰到有阶梯数刚好为l+1的情况，就可以直接结束枚举的过程了(不可能有比l+1更短的情况)，由于数据量不大，手打快排和qsort()没太大区别。

  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <cstring>
  4. using namespace std;
  5. #define OVER 70000
  6. int t,n,l;
  7. char word[101][MAX];
  8. int path[101],root[101];
  9. bool one[110][110],tol[110][110];
  10. bool hash[101],h[27];
  11. struct node{
  12.     int num;
  13.     int cost;
  14. };
  15. node now,next;
  16. node que[70001];
  17. int ql,qh;
  18.  
  19. inline void QuickSort(int low, int high)
  20. {
  21.     char key[MAX];
  22.     int LOW,HIGH;
  23.  
  24.     if(low>high) return ;
  25.     strcpy(key,word[low]);
  26.     LOW=low;HIGH=high;
  27.     while(low<high)
  28.     {
  29.         while(high>low)
  30.         {
  31.             if(strcmp(key,word[high])>0)
  32.             {
  33.                 strcpy(word[low],word[high]);
  34.                 low++;break;
  35.             }
  36.             high--;
  37.         }
  38.         while(low<high)
  39.         {
  40.             if(strcmp(key,word[low])<0)
  41.             {
  42.                 strcpy(word[high],word[low]);
  43.                 high--;break;
  44.             }
  45.             low++;
  46.         }
  47.     }
  48.     strcpy(word[low],key);
  49.     QuickSort(LOW,low-1);
  50.     QuickSort(low+1,HIGH);
  51. }
  52.  
  53. //inline int cmp(const void *a,const void *b)
  54. //{
  55. //    char* c=(char *)a;
  56. //    char* d=(char *)b;
  57. //    return strcmp(c,d);
  58. //}
  59.  
  60. inline int comp(const int &x,const int &y)
  61. {
  62.     int c,flag;
  63.     memset(h,0,sizeof(h));c=0;
  64.     for(int i=0;i<l;i++)
  65.     {
  66.         flag=0;
  67.         for(int j=0;j<l;j++)
  68.             if(!h[j] && word[x][i]==word[y][j])
  69.             {c++;h[j]=1;break;}
  70.     }
  71.     return c;
  72. }
  73.  
  74. inline int bfs(const int &x)
  75. {
  76.     ql=0;qh=0;
  77.     now.num=x;now.cost=1;hash[x]=1;
  78.     que[qh++]=now;if(qh>OVER) qh%=OVER;
  79.     while(ql<qh)
  80.     {
  81.         now=que[ql++];if(ql>OVER) ql%=OVER;
  82.         if(tol[now.num][x]==1) return now.cost;
  83.         for(int i=0;i<n;i++)
  84.         {
  85.             if(hash[i]) continue;
  86.             if(one[now.num][i]==1)
  87.             {
  88.                 next.num=i;next.cost=now.cost+1;
  89.                 que[qh++]=next;if(qh>OVER) qh%=OVER;
  90.                 hash[i]=1;root[i]=now.num;
  91.             }
  92.         }
  93.     }
  94.     return 0;
  95. }
  96.  
  97. int main()
  98. {
  99.     int minpath,tem;
  100.  
  101.     scanf("%d",&t);
  102.     while(t--)
  103.     {
  104.         scanf("%d %d",&n,&l);
  105.         for(int i=0;i<n;i++)
  106.             scanf("%s",word[i]);
  107.         //qsort(word,n,sizeof(word[0]),cmp);
  108.         QuickSort(0,n-1);
  109.         memset(tol,0,sizeof(tol));
  110.         memset(one,0,sizeof(one));
  111.         for(int i=0;i<n-1;i++)
  112.             for(int j=i+1;j<n;j++)
  113.             {
  114.                 tem=comp(i,j);
  115.                 if(tem==l-1) {one[i][j]=1;one[j][i]=1;}
  116.                 if(tem==0) {tol[i][j]=1;tol[j][i]=1;}
  117.             }
  118.         minpath=200;
  119.         for(int i=0;i<n && minpath!=l+1;i++)
  120.         {
  121.             memset(hash,0,sizeof(hash));
  122.             memset(root,-1,sizeof(root));
  123.             path[0]=bfs(i);
  124.             if(path[0]>l && path[0]<minpath)
  125.             {
  126.                 minpath=path[0];
  127.                 for(int j=1;j<=minpath;j++)
  128.                 {path[j]=now.num;now.num=root[now.num];}
  129.             }
  130.         }
  131.         for(int i=minpath;i>0;i--)
  132.         {
  133.             if(i==1) printf("%sn",word[path[i]]);
  134.             else printf("%s ",word[path[i]]);
  135.         }
  136.     }
  137.     return 0;
  138. }

,

No Comments

JstardictBB–>TeeDict

Posted by twcai in My BlackBerry on August 28, 2008

–2008-06-25 22:42
为我的BB 8100安装了JstardictBB，运行没有问题。但一直无法正确的添加从王网上下载的辞典，至今JstardictBB都是一个空壳，郁闷。同学的8100也遇到了同样的问题。最近比较忙，以后慢慢探索吧。
- -!
Update at 2008-6-27 : 现在JstardictBB已升级为TeeDict，安装以后设置为自动搜索词典就可以解决上面所说的问题了。如果再搜索词典的过程中，Black Berry不停得要求你选择是否让TeeDict程序访问本地的文件夹，那么只要在BB的安全选项里，打开防火墙就可以了，这样BB只会询问一次。
下载地址可以在作者的博客找到

http://oranbb.blogbus.com/logs/23611581.html

, , ,

No Comments

BB遇险

Posted by twcai in My BlackBerry on August 28, 2008

–2008-06-20 00:01
晚上在blackberry8100上安装了一个金山词霸，虽然已经有Jstardict了，但为了比较哪个字典更好用，我非常欠揍的把金山安装上了，完美运行。
顺便一提，我的BB8100是4.5的rom，我比较喜欢4.5的英文界面，因为感觉这个界面本来就没考虑到中文，待机画面下的中文字体非常

, , ,

1 Comment

新分类 My BlackBerry

Posted by twcai in My BlackBerry on August 28, 2008

原来的空间上有两篇关于BlackBerry的日志浏览量还挺大的，是我关于自己使用BlackBeryy手机的一点心得和记录。
也拿到这边来充实一下。

No Comments

第一篇日志

Posted by twcai in Some parts on August 28, 2008

弄了三个钟头，弄出了这点东西。发现要想随心所欲的修改css，必须要会php才行，不然永远都局限别人的框架里是一件很不爽的事情。
目前找到的这个模板我还是挺满意的，比较简洁，也不算难看，顺眼就好了，呵呵。以后主要都在这里更新啦。
另外发个代码测试一下coolcode插件:

  1. //Just a Hello World.
  2. #include <iostream>
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     printf("%s\n","Hello World!");
  8.     return 0;
  9. }//end for main

测试下第二段代码

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6.     printf("%s\n","Hello World!");
  7.     return 0;
  8. }//end for main

, ,

No Comments