• <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>

            學習心得(code)

            superlong@CoreCoder

              C++博客 :: 首頁 :: 聯系 :: 聚合  :: 管理
              74 Posts :: 0 Stories :: 5 Comments :: 0 Trackbacks

            公告

            文字可能放在http://blog.csdn.net/superlong100,此處存放代碼

            常用鏈接

            留言簿(4)

            我參與的團隊

            搜索

            •  

            最新隨筆

            最新評論

            • 1.?re: Poj 1279
            • 對于一個凹多邊形用叉積計算面積 后能根據結果的正負來判斷給的點集的時針方向?
            • --bsshanghai
            • 2.?re: Poj 3691
            • 你寫的這個get_fail() 好像并是真正的get_fail,也是說fail指向的串并不是當前結點的子串。為什么要這樣弄呢?
            • --acmer1183
            • 3.?re: HDU2295[未登錄]
            • 這個是IDA* 也就是迭代加深@ylfdrib
            • --superlong
            • 4.?re: HDU2295
            • 評論內容較長,點擊標題查看
            • --ylfdrib
            • 5.?re: HOJ 11482
            • 呵呵..把代碼發在這里很不錯..以后我也試試...百度的編輯器太爛了....
            • --csuft1

            閱讀排行榜

            評論排行榜

            #include <iostream>
            #include 
            <string>
            #define EPS 1e-6
            #define MAXN 101
            #define zero(x) (((x)>0?(x):-(x))<EPS)
            using namespace std;

            int DEBUG;
            int n, m, num;

            struct tree
            {
                tree 
            *next[52], *fail;
                
            int id, L;
            };

            struct point
            {
                
            double x, y;
                
            void data(int i, int j)
                {x 
            = i; y = j;}
                
            void write(){printf("%.0lf %.0lf\n",x, y);}
            };

            tree 
            *root, *p;

            tree arr[
            1000005];
            int  indexx;

            int map(char ch)
            {
                
            if(ch <= 'Z'return ch - 'A';
                
            else          return ch - 'a';
            }

            void newn()
            {
                arr[indexx].fail 
            = NULL;
                arr[indexx].id 
            = 0;
                arr[indexx].L 
            = -1;
                
            for(int i = 0; i < 52; i ++) arr[indexx].next[i] = 0;
            }

            void init()
            {
                indexx 
            = 0;
                newn();
                root 
            = &arr[indexx ++];
            }

            void insert(char ch[], int id, int L)
            {
                
            int t, i = 0;
                p 
            = root;
                
            while(ch[i])
                {
                    t 
            = map(ch[i]);
                    
            if(p->next[t] == 0)
                    {
                        newn();
                        p
            ->next[t] = &arr[indexx ++];
                    }
                    p 
            = p->next[t];
                    i 
            ++;
                }
                p
            ->= L - 1;
                p
            ->id = id;
            }

            tree 
            *que[1000005];

            void get_fail()
            {
                
            int close = -1, open = 0;
                p 
            = root;    p->fail = root;
                que[
            0= p;
                
            while(close < open)
                {
                    p 
            = que[++close];
                    
            for(int i = 0; i < 52; i ++)
                    {
                        
            if(p->next[i] == 0)
                        {
                            
            if(p == root) p->next[i] = root;
                            
            else          p->next[i] = p->fail->next[i];
                        }
                        
            else
                        {
                            
            if(p == root) p->next[i]->fail = root;
                            
            else          p->next[i]->fail = p->fail->next[i];
                            que[
            ++open] = p->next[i];
                        }
                    }
                }
            }

            char  list[101][101];
            point line[
            101][2];

            int mv[8][2= {{01}, {10}, {11}, {-1-1}, {0-1}, {-10}, {1-1}, {-11}};

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


            void query(int inix, int iniy, int way)//way => direction
            {
                
            int t, i = 0, x = inix, y = iniy;
                
                tree 
            *q;
                p 
            = root;
                
            while( ok(x, y) )
                {
                    t 
            = map(list[x][y]);
                    
            while(!p->next[t] && p != root) p = p->fail;
                    p 
            = p->next[t];
                    
            if(!p) p = root; q = p;
                    
            while( q != root && q->fail)
                    {
                        
            if(q->id)
                        {
                            
            int i = q->id;
                            point end;
                            end.data(x, y);    
                            line[i][
            1= end;
                            
                            point sta;
                            sta.data(x 
            - q->* mv[way][0], y - q->* mv[way][1]);
                            line[i][
            0= sta;
                            
                            q
            ->id = 0;
                        }
                        q 
            = q->fail;
                    }
                    i 
            ++;
                    x 
            += mv[way][0];
                    y 
            += mv[way][1];
                }
            }

            int tu[101][101];

            //計算cross product (P1-P0)x(P2-P0)
            double xmult(point p1,point p2,point p0){
                
            return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
            }

            //判三點共線
            int dots_inline(point p1,point p2,point p3){
                
            return zero(xmult(p1,p2,p3));
            }

            //判點是否在線段上,包括端點
            int dot_online_in(point p,point l1,point l2){
                
            return zero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<EPS&&(l1.y-p.y)*(l2.y-p.y)<EPS;
            }

            //判兩點在線段同側,點在線段上返回0
            int same_side(point p1,point p2,point l1,point l2){
                
            return xmult(l1,p1,l2)*xmult(l1,p2,l2)>EPS;
            }

            //判兩線段相交,包括端點和部分重合
            int intersect_in(point u1,point u2,point v1,point v2){
                
            if (!dots_inline(u1,u2,v1)||!dots_inline(u1,u2,v2))
                    
            return !same_side(u1,u2,v1,v2)&&!same_side(v1,v2,u1,u2);
                
            return dot_online_in(u1,v1,v2)||dot_online_in(u2,v1,v2)||dot_online_in(v1,u1,u2)||dot_online_in(v2,u1,u2);
            }

            //計算兩直線交點,注意事先判斷直線是否平行!
            point intersection(point u1,point u2,point v1,point v2){
                point ret
            =u1;
                
            double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
                        
            /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
                ret.x
            +=(u2.x-u1.x)*t;
                ret.y
            +=(u2.y-u1.y)*t;
                
            return ret;
            }

            bool connect(int i, int j)
            {
                point s1, s2, e1, e2, p;
                s1 
            = line[i][0];
                e1 
            = line[i][1];
                s2 
            = line[j][0];
                e2 
            = line[j][1];
                
                
            if(intersect_in(s1, e1, s2, e2))
                    p 
            = intersection(s1, e1, s2, e2);
                
            else return false;
                    
                
            if( p.x - (int)p.x > EPS || p.y - (int)p.y > EPS) return false;
                
            return true;
                
            }

            void bulid()
            {
                
            int i, j;
                memset(tu, 
            0sizeof(tu));
                
            //線段相交構圖 
                for(i = 1; i <= num; i ++)
                {
                    
            for(j = i + 1; j <= num; j ++)
                    
            if( connect(i, j) )
                    {
                        tu[i][j] 
            = true;
                        tu[j][i] 
            = true;
                    }
                }
            }

            int cnt;
            bool h[101];

            void dfs(int x)
            {
                
            int i;
                
            for(i = 1; i <= num; i ++)
                
            if(!h[i] && tu[x][i])
                {
                    h[i] 
            = 1;
                    cnt 
            ++;
                    dfs(i);
                }
            }

            void search(int n,int mat[][MAXN],int* dfn,int* low,int now,int& ret,int* key,int& cnt,int root,int& rd,int* bb){
                
            int i;
                dfn[now]
            =low[now]=++cnt;
                
            for (i=1;i<=n;i++)
                    
            if (mat[now][i]){
                        
            if (!dfn[i]){
                            search(n,mat,dfn,low,i,ret,key,cnt,root,rd,bb);
                            
            if (low[i]<low[now])
                                low[now]
            =low[i];
                            
            if (low[i]>=dfn[now]){
                                
            if (now!=root&&!bb[now])
                                    key[ret
            ++]=now,bb[now]=1;
                                
            else if(now==root)
                                    rd
            ++;
                            }
                        }
                        
            else if (dfn[i]<low[now])
                            low[now]
            =dfn[i];
                    }
            }

            int key_vertex(int n,int mat[][MAXN],int* key){
                
            int ret=0,i,cnt,rd,dfn[MAXN],low[MAXN],bb[MAXN];
                
            for (i=1;i<=n;dfn[i++]=bb[i]=0);
                
            for (cnt=0,i=1;i<=n;i++)
                    
            if (!dfn[i]){
                        rd
            =0;
                        search(n,mat,dfn,low,i,ret,key,cnt,i,rd,bb);
                        
            if (rd>1&&!bb[i])
                            key[ret
            ++]=i,bb[i]=1;
                    }
                
            return ret;
            }

            bool solve()
            {
                
            //查詢 
                for(int i = 0; i < n; i ++)
                
            for(int J = 0; J < m; J ++)
                {
                    query(i, J, 
            0); query(i, J, 4);
                    query(i, J, 
            1); query(i, J, 5);
                    query(i, J, 
            2); query(i, J, 6);
                    query(i, J, 
            3); query(i, J, 7);
                }
                
            //建圖 
                bulid();
                memset(h ,
            0 ,sizeof(h));
                cnt 
            = 1;
                h[
            1= 1;
                
            //連通性 
                dfs(1);
                
            if(cnt != num)     return false;
                
            int key[101];
                
            //割點 
                cnt = key_vertex(num, tu, key);
                
            if(cnt > 0return false;
                
            return true;
                
            }

            int main()
            {
                DEBUG 
            = 0;
                freopen(
            "in1.txt","r",stdin);
                
            while(scanf("%d %d %d"&n, &m, &num), n+m+num)
                {
                    
            for(int i = 0; i < n; i ++) scanf("%s", list[i]);
                    
            char temp[101];
                    
            //AC自動機 
                    init();
                    
            for(int i = 1; i <= num; i ++)
                    {
                        scanf(
            "%s", temp);
                        
            int l = strlen(temp);
                        insert(temp, i, l);        
                    }
                    get_fail();
                    
            //構圖求解 
                    if(solve()) puts("Yes");
                    
            else        puts("No");
                }
                
            while(1);
            }

            posted on 2009-09-10 16:33 superlong 閱讀(209) 評論(0)  編輯 收藏 引用
            伊人久久大香线蕉精品不卡 | 99久久99久久精品免费看蜜桃| 午夜精品久久久久久| 久久人人爽人人爽人人片AV麻豆| 国产AV影片久久久久久| 中文字幕无码久久精品青草| 久久精品www人人爽人人| 精品久久久久久无码人妻蜜桃| 一本色道久久综合| 色综合久久88色综合天天| 日韩久久久久中文字幕人妻| 久久99亚洲网美利坚合众国| 久久久噜噜噜久久中文字幕色伊伊| 久久91精品国产91| 国内精品久久久久久久coent| 一本色道久久综合亚洲精品| 久久国产精品无码网站| 精品免费tv久久久久久久| 伊色综合久久之综合久久| 国产成人久久777777| 精品国际久久久久999波多野| 一本一道久久a久久精品综合| 久久亚洲高清观看| 99久久人妻无码精品系列| 亚洲国产精品高清久久久| 久久笫一福利免费导航| 久久久久国产精品麻豆AR影院| 嫩草影院久久99| 91久久精品91久久性色| 国产精品99久久99久久久| 熟妇人妻久久中文字幕| 久久久久久免费视频| 日本久久中文字幕| 久久婷婷五月综合色99啪ak| 久久香蕉国产线看观看99| 99久久精品这里只有精品| 久久中文字幕一区二区| 国产精品欧美久久久久天天影视| 久久综合中文字幕| 久久国产免费直播| 久久ww精品w免费人成|