• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            poj1204

            Word Puzzles

            Time Limit: 5000MS Memory Limit: 65536K
            Total Submissions: 6968 Accepted: 2651 Special Judge

            Description

            Word puzzles are usually simple and very entertaining for all ages. They are so entertaining that Pizza-Hut company started using table covers with word puzzles printed on them, possibly with the intent to minimise their client's perception of any possible delay in bringing them their order.

            Even though word puzzles may be entertaining to solve by hand, they may become boring when they get very large. Computers do not yet get bored in solving tasks, therefore we thought you could devise a program to speedup (hopefully!) solution finding in such puzzles.

            The following figure illustrates the PizzaHut puzzle. The names of the pizzas to be found in the puzzle are: MARGARITA, ALEMA, BARBECUE, TROPICAL, SUPREMA, LOUISIANA, CHEESEHAM, EUROPA, HAVAIANA, CAMPONESA.

            Your task is to produce a program that given the word puzzle and words to be found in the puzzle, determines, for each word, the position of the first letter and its orientation in the puzzle.

            You can assume that the left upper corner of the puzzle is the origin, (0,0). Furthemore, the orientation of the word is marked clockwise starting with letter A for north (note: there are 8 possible directions in total).

            Input

            The first line of input consists of three positive numbers, the number of lines, 0 < L <= 1000, the number of columns, 0 < C <= 1000, and the number of words to be found, 0 < W <= 1000. The following L input lines, each one of size C characters, contain the word puzzle. Then at last the W words are input one per line.

            Output

            Your program should output, for each word (using the same order as the words were input) a triplet defining the coordinates, line and column, where the first letter of the word appears, followed by a letter indicating the orientation of the word according to the rules define above. Each value in the triplet must be separated by one space only.

            Sample Input

            20 20 10
            QWSPILAATIRAGRAMYKEI
            AGTRCLQAXLPOIJLFVBUQ
            TQTKAZXVMRWALEMAPKCW
            LIEACNKAZXKPOTPIZCEO
            FGKLSTCBTROPICALBLBC
            JEWHJEEWSMLPOEKORORA
            LUPQWRNJOAAGJKMUSJAE
            KRQEIOLOAOQPRTVILCBZ
            QOPUCAJSPPOUTMTSLPSF
            LPOUYTRFGMMLKIUISXSW
            WAHCPOIYTGAKLMNAHBVA
            EIAKHPLBGSMCLOGNGJML
            LDTIKENVCSWQAZUAOEAL
            HOPLPGEJKMNUTIIORMNC
            LOIUFTGSQACAXMOPBEIO
            QOASDHOPEPNBUYUYOBXB
            IONIAELOJHSWASMOUTRK
            HPOIYTJPLNAQWDRIBITG
            LPOINUYMRTEMPTMLMNBO
            PAFCOPLHAVAIANALBPFS
            MARGARITA
            ALEMA
            BARBECUE
            TROPICAL
            SUPREMA
            LOUISIANA
            CHEESEHAM
            EUROPA
            HAVAIANA
            CAMPONESA

            Sample Output

            0 15 G
            2 11 C
            7 18 A
            4 8 C
            16 13 B
            4 15 E
            10 3 D
            5 1 E
            19 7 C
            11 11 H

            Source


            基本多串匹配
            給定一個字母矩陣
            在給定一些單詞,問這些單詞在矩陣中的位置和方向,
            囧呆了,單詞構建trie樹,
            把矩陣中的每一個8個方向之一的字符串看作文章
            然后去做自動機
            只需要枚舉周圍一圈的點的方向即可(想了好久才明白,自己去琢磨),

            看來自己對ac自動機還不是理解的很透徹,得再看幾遍

            #include <cstdio>
            #include 
            <cstdlib>
            #include 
            <cstring>
            #include 
            <cmath>
            #include 
            <ctime>
            #include 
            <cassert>
            #include 
            <iostream>
            #include 
            <sstream>
            #include 
            <fstream>
            #include 
            <map>
            #include 
            <set>
            #include 
            <vector>
            #include 
            <queue>
            #include 
            <algorithm>
            #include 
            <iomanip>
            #define maxn 1005
            using namespace std;
            int n,m,w;
            char s1[maxn][maxn];
            char str[maxn];
            int dx[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
            struct node
            {
                
            int next[26];
                
            int count;
                
            int fail;
                
            void init()
                
            {
                    memset(next,
            -1,sizeof(next));
                    count
            =0;fail=0;
                }

            }
            s[5000005];
            struct result
            {
                
            int x,y,d;
            }
            res[maxn];
            int sind;
            int q[500005],head,tail;
            int len[maxn];
            void cas_init()
            {
                s[
            0].init();
                sind
            =1;
            }

            void ins(char srt[],int k)
            {
                
            int len=strlen(str);
                
            int i,j,ind;
                ind
            =0;
                
            for(i=0;i<len;i++)
                
            {
                    j
            =str[i]-'A';
                    
            if(s[ind].next[j]==-1)
                    
            {
                        s[sind].init();
                        s[ind].next[j]
            =sind++;
                    }

                    ind
            =s[ind].next[j];
                }

                s[ind].count
            =k;
            }

            void make_fail()
            {
                head
            =0;tail=0;
                
            int i,ind,ind_f;
                
            for(i=0;i<26;i++)
                
            {
                    
            if(s[0].next[i]!=-1)
                    
            {
                        q[
            ++tail]=s[0].next[i];
                    }

                }

                
            while(head<tail)
                
            {
                    ind
            =q[++head];
                    
            for(i=0;i<26;i++)
                    
            {
                        
            if(s[ind].next[i]!=-1)
                        
            {
                            q[
            ++tail]=s[ind].next[i];
                            ind_f
            =s[ind].fail;
                            
            while(ind_f>0&&s[ind_f].next[i]==-1)
                            ind_f
            =s[ind_f].fail;
                            
            if(s[ind_f].next[i]!=-1)
                            ind_f
            =s[ind_f].next[i];
                            s[s[ind].next[i]].fail
            =ind_f;
                        }

                    }

                }

            }

            bool check(int x,int y)
            {
                
            return (x>=0&&x<n&&y>=0&&y<m);
            }

            void fd(int x1,int y1,int d)
            {
                
            int di,i,ind,p,x,y;
                ind
            =0;x=x1;y=y1;
                
            for(;check(x,y);x+=dx[d][0],y+=dx[d][1])
                
            {
                    i
            =s1[x][y]-'A';
                    
            while(ind>0&&s[ind].next[i]==-1)
                    ind 
            =s[ind].fail;
                    
            if(s[ind].next[i]!=-1)
                    
            {
                        ind
            =s[ind].next[i];
                        p
            =ind;
                        
            //printf("%d\n",ind);
                        while(p>0&&s[p].count!=-1)
                        
            {
                            
            int tmp=s[p].count;
                            res[tmp].x
            =x-(len[tmp]-1)*dx[d][0];
                            res[tmp].y
            =y-(len[tmp]-1)*dx[d][1];
                            res[tmp].d
            =d;
                            
            //cout<<s[p].count<<" "<<x1<<" "<<y1<<" "d<<endl;
                            s[p].count=-1;
                            p
            =s[p].fail;
                        }

                    }

                }

            }

            int main()
            {
                scanf(
            "%d%d%d",&n,&m,&w);
                
            for(int i=0;i<n;i++) scanf("%s",s1[i]);
                cas_init();
                
            for(int i=1;i<=w;i++)
                
            {
                    scanf(
            "%s",str);
                    len[i]
            =strlen(str);
                    ins(str,i);
                }

                make_fail();
                
            for(int i=0;i<m;i++)
                
            {
                    fd(
            0,i,3);fd(0,i,4);fd(0,i,5);
                    fd(n
            -1,i,7);fd(n-1,i,0);fd(n-1,i,1);
                }

                
            for(int i=0;i<n;i++)
                
            {
                    fd(i,
            0,1);fd(i,0,2);fd(i,0,3);
                    fd(i,m
            -1,5);fd(i,m-1,6);fd(i,m-1,7);
                }

                
            for(int i=1;i<=w;i++)
                printf(
            "%d %d %c\n",res[i].x,res[i].y,res[i].d+'A');
                
            return 0;
            }



            這個題說的還是比較模糊的了,沒有說明多個匹配的情況怎么辦,
            但是它special judge了,應該是輸出任意一中情況即可

            posted on 2012-07-18 00:06 jh818012 閱讀(240) 評論(0)  編輯 收藏 引用

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導航

            統計

            常用鏈接

            留言簿

            文章檔案(85)

            搜索

            最新評論

            • 1.?re: poj1426
            • 我嚓,,輝哥,,居然搜到你的題解了
            • --season
            • 2.?re: poj3083
            • @王私江
              (8+i)&3 相當于是 取余3的意思 因為 3 的 二進制是 000011 和(8+i)
            • --游客
            • 3.?re: poj3414[未登錄]
            • @王私江
              0ms
            • --jh818012
            • 4.?re: poj3414
            • 200+行,跑了多少ms呢?我的130+行哦,你菜啦,哈哈。
            • --王私江
            • 5.?re: poj1426
            • 評論內容較長,點擊標題查看
            • --王私江
            久久综合色老色| 性做久久久久久久久| 久久久久人妻一区精品色| 久久精品一本到99热免费| 亚洲精品白浆高清久久久久久| 久久99久国产麻精品66| 久久精品国产亚洲欧美| 日韩欧美亚洲综合久久影院Ds| 色偷偷偷久久伊人大杳蕉| 久久国产成人精品麻豆| 中文字幕精品久久| 九九久久99综合一区二区| 久久精品综合网| 久久天堂电影网| 久久久久亚洲av成人网人人软件| 97久久超碰国产精品2021| 久久天天日天天操综合伊人av| 欧美精品久久久久久久自慰| 久久久精品久久久久久 | 久久99国产乱子伦精品免费| 国产精品美女久久久免费| 欧洲人妻丰满av无码久久不卡| 久久综合香蕉国产蜜臀AV| 久久久久国产成人精品亚洲午夜| 国产精品禁18久久久夂久| 18岁日韩内射颜射午夜久久成人| 久久久久亚洲精品天堂久久久久久| 久久久久久伊人高潮影院| 久久婷婷色综合一区二区| 久久久亚洲欧洲日产国码aⅴ| 亚洲国产高清精品线久久| 成人精品一区二区久久久| 狠狠色丁香久久综合五月| 久久午夜伦鲁片免费无码| 国内精品久久久久影院薰衣草| 久久久精品日本一区二区三区 | 欧美国产成人久久精品| 亚洲午夜精品久久久久久人妖| 久久国产亚洲高清观看| 亚洲欧美伊人久久综合一区二区| 久久精品国产精品亚洲精品|