trie[1415][1000]

2^0.5 ~= 1.414

最多1000个单词，每个单词最长对角线长度啊。

> 其实还是有个小地方不解，再看看代码。
> 另外， trie数组的大小到底怎么确定，我是开大数组的。
> int trie[?][27];前面那个?最大会是多少呢？
> 
> 附，代码如下
> #include<cstdio>
> #include<cstdlib>
> #include<string>
> #include<iostream>
> using namespace std;
> int trie[100010][28];
> int index[100010];
> 
> char table[1010][1010];//这两个为输入 
> //char word[1010][1010];
> string word;
> int LL[1010],CC[1010];//这三个记录结果 
> char dir[1010];
> 
> int L,C,W;
> int row[8]={-1,-1,0,1,1,1,0,-1},col[8]={0,1,1,1,0,-1,-1,-1};
> int main()
> {
>     scanf("%d%d%d",&L,&C,&W);
>     for(int i=0;i<L;++i)
>        scanf("%s",table[i]);
>     
>     int length=0;
>     for(int i=0;i<W;++i)
>     {
>          cin>>word;
>         //scanf("%s",word[i]);
>         int start=0,j=0;
>         int len=word.length();
>         while(j!=len)
>         {
>              int next=word[j]-'A'+1;
>              if(trie[start][next]==0)
>                 trie[start][next]=++length;
>              start=trie[start][next];
>              ++j;
>         }
> //        printf("start=%d\n",start);
>         trie[start][0]=-1;
>         index[start]=i;
>     }
> //    printf("%s\n%s\n",table[5],word);
>     for(int i=0;i<L;++i)
>     {
>        for(int j=0;j<C;++j)
>        {
>           for(int d=0;d<8;++d)
>           {
>               int start=0;
>               int r=i,c=j;
> //              printf("i=%d j=%d dir=%c\n",i,j,d+'A');
>               do
>               {
>                   int next=table[r][c]-'A'+1;
>                   start=trie[start][next];
> //                  printf("start=%d\n",start);
>                   if(start==0)
>                     break;
>                   if(trie[start][0]==-1)
>                   {
>                      int k=index[start];
>                      LL[k]=i;
>                      CC[k]=j;
>                      dir[k]='A'+d;
> //                     printf("k=%d %s\n",k,word[k]);
> //                     printf("%d %d %c\n",i,j,'A'+d);
>                   }
>                   r+=row[d];
>                   c+=col[d];
>               }while(r>=0&&c>=0&&r<L&&c<C);
>           }
>        }
>     }
>     for(int i=0;i<W;++i)
>     {
>        printf("%d %d %c\n",LL[i],CC[i],dir[i]);
>     }
> //    system("pause");
>     return 0;
> }

• Re:居然AC，虽然用时和内存都很大，但对我这种菜鸟来说，做出这个题还是很不容易的，只是，其实 (112) PoPoQQQ 2014-07-27 16:02:52
  • 指针版表示不用纠结数组大小 (14) 1007783493 2015-02-19 12:37:02