解題思路:建立輸入單詞(反向，便于尋找起始點所在的位置)的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元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
