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條評論
主站蜘蛛池模板: 中文字幕在线精品视频万部 | 婷婷色香五月激情综合2020 | 日本一道一区 | 99在线视频播放 | 四虎影院国产精品 | 欧美国产日产精品免费视频 | 中文字幕久热精品视频免费 | 毛片在线高清免费观看 | 久久官网| 天天爽天天干天天操 | 欧美毛片 | 94久久国产乱子伦精品免费 | 老司机免费福利影院 | 日本福利片国产午夜久久 | 国产精品一区二区四区 | 亚洲精品综合欧美一区二区三区 | 欧美性色xo影院69 | 国内精品久久久久影院老司 | 伦伦影院精品一区 | 亚洲欧美天堂网 | 99热久久国产精品这里有全部 | 色激情综合网 | 日本一线一区二区三区免费视频 | 亚色在线播放 | 国产成人免费全部网站 | 免费视频不卡 | 国产一区二区播放 | 亚洲精品乱码久久久久久蜜桃 | 精品精品国产高清a毛片 | 色综合天天综合网亚洲 | 久久久精品免费热线观看 | 午夜激情网站 | 国产五月色婷婷六月丁香视频 | 99精品热女视频专线 | 免费福利小视频 | 欧美成人免费观看的 | 欧美 日产 国产精品 | 91欧美在线视频 | 欧美成a | 亚洲欧美日韩国产一区图片 | 久久爱www成人 |