usingnamespacestd;#defineMAX_SIZE1005#defineMAX_LEN1005#defineMAX_NOD1000001#de" />

亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

POJ 1204 Word Puzzles

系統 1586 0

解題思路:建立輸入單詞(反向,便于尋找起始點所在的位置)的AC圖,然后按照八個方向依次尋找(注意方向也為方向)。例如A是向上方向,我們需要改為反向,向下。那么我們需要將每列--從上到下方向--組成的字符串--共width個--分別到AC圖中查找匹配。

關鍵代碼已經注釋

?

      
#include < iostream >
using namespace std;



#define MAX_SIZE 1005
#define MAX_LEN 1005
#define MAX_NOD 1000001
#define initArray(array) memset(array, 0, sizeof(array))

/* ********************************************************************** */
/* Descrption: 采用左孩子,右兄弟的結構實現AC自動機,母串前進的過程仍需采用
回溯的方法找到下一個匹配點, trie圖是不需要回溯的
/* first - 當前節點的第一個孩子節點
/* next - 當前節點的兄弟節點
/* suffix - 后綴節點
/* queue - BFS 過程存儲節點
/* id - 該危險節點所對應的單詞,0表示其為安全節點
/* place - 單詞所對應的危險節點編號
/* node - trie圖節點的存儲
/* letter - 當前字典樹插入的單詞
/* 其他(略)
/***********************************************************************
*/
int size, width, height;
int first[MAX_NOD], next[MAX_NOD], suffix[MAX_NOD], queue[MAX_NOD], id[MAX_NOD], place[MAX_LEN];
int wx[MAX_SIZE], wy[MAX_SIZE], wd[MAX_SIZE];
char node[MAX_NOD], letter[MAX_LEN];
char map[MAX_SIZE][MAX_SIZE];

// 8個方向,方向均為反方向,便于找到初始點位置
const int dir[ 8 ][ 2 ] = {{ 0 , 1 }, { - 1 , 1 }, { - 1 , 0 }, { - 1 , - 1 }, { 0 , - 1 }, { 1 , - 1 }, { 1 , 0 }, { 1 , 1 }};

void Build_Trie( int n) // 字典樹中插入第n個單詞
{
int p = 0 , t;

for ( int i = strlen(letter) - 1 ; i >= 0 ; i -- ) // 從后往前插入,便于找到初始點
{
t
= first[p];
while (t && node[t] != letter[i]) t = next[t];
if ( ! t)
{
node[
++ size] = letter[i];
next[size]
= first[p];
first[p]
= size;
first[size]
= 0 ;
p
= size;
}
else
p
= t;
}
id[p]
= n, place[n] = p;
}

int Child( int x, char c) // 求取x的c孩子
{
int t;
while ( true )
{
t
= first[x];
while (t && node[t] != c)t = next[t];
if (t || ! x) break ;
x
= suffix[x]; // 如果當前節點不存在c孩子,則到后綴結點中尋找
}
return t;
}

void Build_Graph() // 建立AC圖
{
int head = 0 , tail = 0 ;
queue[
0 ] = 0 ;
while (head <= tail)
{
if (first[queue[head]])
{
queue[
++ tail] = first[queue[head]];
while ( true )
{
if (head == 0 ) suffix[queue[tail]] = 0 ;
else
{
suffix[queue[tail]]
= Child(suffix[queue[head]], node[queue[tail]]);
if (id[queue[tail]] == 0 && id[suffix[queue[tail]]]) // 如果后綴結點是危險節點,則該節點也是危險節點
id[queue[tail]] = id[suffix[queue[tail]]];
}
if ( ! next[queue[tail]]) break ;
queue[
++ tail] = next[queue[tail - 1 ]];
}
}
head
++ ;
}
}

void scan( int x, int y, int dirIndex)
{
int t, p = 0 ;
while (x >= 0 && x < width && y >= 0 && y < height)
{
p
= Child(p, map[y][x]); t = id[p];
while (t > 0 )
{
wx[t]
= x, wy[t] = y, wd[t] = dirIndex; // 防止字串包含的情況,如(abc與bc)
t = id[suffix[place[t]]];
}
x
+= dir[dirIndex][ 0 ];
y
+= dir[dirIndex][ 1 ];
}
}
int main()
{
int dirIndex, i, w;
bool flag;
size
= 0 ;
scanf(
" %d %d %d " , & height, & width, & w);
for (i = 0 ; i < height; i ++ )
scanf(
" %s " , map[i]);
initArray(first), initArray(next), initArray(id);
for (i = 0 ; i < w; i ++ )
{
scanf(
" %s " , letter);
Build_Trie(i
+ 1 );
}
Build_Graph();
memset(wd,
- 1 , sizeof (wd));
dirIndex
= 0 ; for (i = 0 ; i < width; i ++ )scan(i, 0 , dirIndex);
for (i = 0 , flag = true ; (i <= w) && flag; i ++ ) if (wd[i] == - 1 )flag = false ;
if ( ! flag)
{
dirIndex
= 1 ; for (i = 1 ; i < width; i ++ )scan(i, 0 , dirIndex);
for (i = 1 ; i < (height - 1 ); i ++ ) scan(width - 1 , i, dirIndex);
for (i = 1 , flag = true ; (i <= w) && flag; i ++ ) if (wd[i] == - 1 )flag = false ;
}
if ( ! flag)
{
dirIndex
= 2 ; for (i = 0 ; i < height; i ++ )scan(width - 1 , i, dirIndex);
for (i = 1 , flag = true ; (i <= w) && flag; i ++ ) if (wd[i] == - 1 )flag = false ;
}
if ( ! flag)
{
dirIndex
= 3 ; for (i = 1 ; i < width; i ++ )scan(i, height - 1 , dirIndex);
for (i = 1 ; i < height - 1 ; i ++ )scan(width - 1 , i, dirIndex);
for (i = 1 , flag = true ; (i <= w) && flag; i ++ ) if (wd[i] == - 1 )flag = false ;
}
if ( ! flag)
{
dirIndex
= 4 ; for (i = 0 ; i < width; i ++ ) scan(i, height - 1 , dirIndex);
for (i = 1 , flag = true ; (i <= w) && flag; i ++ ) if (wd[i] == - 1 )flag = false ;
}
if ( ! flag)
{
dirIndex
= 5 ; for (i = 1 ; i < height; i ++ )scan( 0 , i, dirIndex);
for (i = 1 ; i < width - 1 ; i ++ )scan(i, height - 1 , dirIndex);
for (i = 1 , flag = true ; (i <= w) && flag; i ++ ) if (wd[i] == - 1 )flag = false ;
}
if ( ! flag)
{
dirIndex
= 6 ; for (i = 0 ; i < height; i ++ )scan( 0 , i, dirIndex);
for (i = 1 , flag = true ; (i <= w) && flag; i ++ ) if (wd[i] == - 1 )flag = false ;
}
if ( ! flag)
{
dirIndex
= 7 ; for (i = 0 ; i < height - 1 ; i ++ )scan( 0 , i, dirIndex);
for (i = 1 ; i < width - 1 ; i ++ )scan(i, 0 , dirIndex);
}
for (i = 1 ; i <= w; i ++ )
printf(
" %d %d %c\n " , wy[i], wx[i], char (wd[i] + ' A ' ));

return 0 ;
}

?

?

POJ 1204 Word Puzzles


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!?。?/p>

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 欧美精品国产综合久久 | 欧美日韩亚洲综合 | 成人国产在线不卡视频 | 欧美日韩操 | 中国一级毛片 | 久久99色 | 久久不卡 | 伊人久久综合谁合综合久久 | 久久草草| 四虎成人欧美精品在永久在线 | 欧美日韩激情在线 | 国产日韩亚洲 | 口国产成人高清在线播放 | 久久国产精品ww | 国产精品国产高清国产专区 | 九九视频免费看 | 日本一级网站 | 精品国产日韩亚洲一区二区 | 亚洲欧美精品天堂久久综合一区 | 国产一区二区三区在线观看精品 | 精品牛牛影视久久精品 | 黄 色 免 费 网站在线观看 | 国产成人精品一区二区三区 | 欧美色图片区 | 亚洲欧美日韩中文高清一 | 九九影院韩国理伦片 | 四虎影视在线影院4hutv | 99热久久国产精品这里有全部 | 久久99精品久久久久久国产越南 | 亚洲va欧美| 国产美女色视频 | 毛片.com| 亚洲99久久久久综合 | 国产探花视频在线观看 | 亚洲免费成人在线 | 中文字幕在线观看 | 不卡高清av手机在线观看 | 日本成人二区 | 五十路一区二区三区视频 | 性欧美极品xxxx欧美一区二区 | 亚洲精品视频免费 |