解題思路:建立輸入單詞(反向,便于尋找起始點所在的位置)的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 ;
}
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

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