青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

學習心得(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 閱讀(215) 評論(0)  編輯 收藏 引用
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            久久久综合香蕉尹人综合网| 免费试看一区| 亚洲伊人久久综合| 国产精品久久综合| 久久久久国产精品麻豆ai换脸| 欧美成人综合一区| 欧美在线观看网址综合| 99热在这里有精品免费| 精品电影在线观看| 欧美国产欧美亚洲国产日韩mv天天看完整 | 亚洲国产三级网| 欧美午夜精品一区| 欧美日韩高清在线播放| 毛片基地黄久久久久久天堂| 久久嫩草精品久久久久| 日韩西西人体444www| 国产午夜亚洲精品羞羞网站 | 亚洲天堂成人在线观看| 亚洲韩国精品一区| 欧美性jizz18性欧美| 久久久人人人| 欧美韩国日本一区| 欧美日韩午夜剧场| 欧美日韩网址| 国产日产亚洲精品| 在线观看一区| 欧美国产欧美综合 | 欧美自拍丝袜亚洲| 欧美成人有码| 亚洲男女自偷自拍图片另类| 亚洲一品av免费观看| 久久久福利视频| 亚洲视频一区在线观看| 亚洲国产精品成人| 亚洲欧美日韩精品久久| 在线视频欧美日韩精品| 美女诱惑黄网站一区| 美女久久一区| 欧美体内she精视频在线观看| 欧美黄网免费在线观看| 亚洲精品老司机| 亚洲精品一区中文| 国内精品美女av在线播放| 狠狠色综合色综合网络| 日韩一二三区视频| 久久在线视频| 日韩一级黄色av| 久久爱www久久做| 欧美激情1区| 一区二区日韩伦理片| 亚洲国产精品一区| 免费观看成人www动漫视频| 狠狠爱www人成狠狠爱综合网| 一本久久a久久免费精品不卡| 欧美激情视频在线播放 | 欧美日韩亚洲国产精品| 亚洲精品免费网站| 亚洲欧洲午夜| 国产精品亚洲а∨天堂免在线| 国产精品99久久久久久人| 日韩五码在线| 性欧美xxxx大乳国产app| 久久露脸国产精品| 99精品国产热久久91蜜凸| 麻豆精品精华液| 亚洲高清资源综合久久精品| 久久久久久亚洲精品杨幂换脸| 影音国产精品| 亚洲欧美精品伊人久久| 亚洲黄网站黄| 欧美亚洲一区二区三区| 在线日韩精品视频| 一本色道婷婷久久欧美| 亚洲国产精品精华液网站| 亚洲欧美在线一区二区| 在线免费观看日韩欧美| 亚洲在线黄色| 亚洲无玛一区| 香蕉久久一区二区不卡无毒影院| 欧美一区二区三区免费看| 伊人一区二区三区久久精品| 欧美大片在线看免费观看| 久久亚洲精选| 国产精品草莓在线免费观看| 久久国产综合精品| 欧美精品免费在线| 一区二区三区高清不卡| 亚洲精品久久久一区二区三区| 欧美色另类天堂2015| 欧美国产综合一区二区| 亚洲福利一区| 亚洲欧美日韩另类| 亚洲午夜久久久久久久久电影院| 久久日韩粉嫩一区二区三区| 性欧美8khd高清极品| 中国成人黄色视屏| 亚洲天堂av在线免费观看| 免费不卡在线观看| 久久亚洲国产成人| 影音先锋在线一区| 欧美91视频| 99人久久精品视频最新地址| 亚洲九九九在线观看| 欧美成人免费va影院高清| 欧美高清在线精品一区| 怡红院精品视频在线观看极品| 亚洲免费在线视频| 夜夜嗨av一区二区三区四季av| 久久综合给合久久狠狠色| 亚洲视频1区2区| 亚洲美女中出| 99精品99久久久久久宅男| 日韩一级在线| 亚洲国产一区二区a毛片| 美女精品在线观看| 男女视频一区二区| 欧美不卡视频一区| 欧美大胆a视频| 亚洲国产mv| 最新日韩欧美| 99精品国产在热久久下载| 亚洲人成在线免费观看| 亚洲国产美女精品久久久久∴| 欧美成人激情视频免费观看| 男人的天堂亚洲在线| 欧美大片在线影院| 亚洲日本理论电影| 一本色道久久综合精品竹菊 | 久久大逼视频| 久久av一区二区三区| 久久精品99国产精品酒店日本| 欧美一区二区三区另类| 久久综合久久久久88| 欧美国产高潮xxxx1819| 欧美日韩网站| 在线观看中文字幕不卡| 亚洲午夜精品久久久久久浪潮| 亚洲欧美日韩电影| 欧美福利视频在线| 一本久道久久久| 开心色5月久久精品| 国产精品麻豆欧美日韩ww| 在线日本高清免费不卡| 久久精品国产免费看久久精品| 欧美成人在线影院| 午夜视频精品| 欧美三区美女| 亚洲精选一区二区| 亚洲高清视频在线观看| 欧美一区二区三区在线| 欧美日一区二区三区在线观看国产免| 国产午夜精品美女视频明星a级| 一区二区三区在线免费视频| 久久久视频精品| 黄色国产精品| 久久久国产精品亚洲一区| 香蕉成人伊视频在线观看| 国产精品久久久久久久第一福利| 91久久极品少妇xxxxⅹ软件| 欧美成人视屏| 欧美成人精品一区二区| aa亚洲婷婷| 亚洲欧美日韩区| 伊人色综合久久天天五月婷| 久久精品青青大伊人av| 亚洲永久免费av| 在线看国产日韩| 亚洲精华国产欧美| 国产精品一区二区三区久久久| 亚洲女性喷水在线观看一区| 日韩视频在线免费观看| 国产精品一区二区男女羞羞无遮挡 | 久久免费视频在线| 鲁大师成人一区二区三区| 日韩午夜在线| 亚洲永久网站| 99视频在线精品国自产拍免费观看 | 亚洲伦理精品| 一色屋精品视频在线看| 夜夜嗨av一区二区三区中文字幕| 国产一区二区三区高清播放| 亚洲国产99| 合欧美一区二区三区| 亚洲欧洲综合| 最新亚洲激情| 久久一区亚洲| 久久国产精品99国产精| 欧美日韩岛国| 午夜亚洲性色视频| 国产日产欧美一区| 亚洲国产成人在线| 亚洲人午夜精品免费| 欧美大香线蕉线伊人久久国产精品| 欧美三级电影精品| 亚洲激情视频网| 亚洲毛片在线观看| 欧美激情国产高清| 亚洲精华国产欧美| 亚洲一级高清| 国内成人精品一区|