解題思路:建立輸入單詞(反向，便于尋找起始點(diǎn)所在的位置)的AC圖，然后按照八個(gè)方向依次尋找(注意方向也為方向）。例如A是向上方向，我們需要改為反向，向下。那么我們需要將每列--從上到下方向--組成的字符串--共width個(gè)--分別到AC圖中查找匹配。
關(guān)鍵代碼已經(jīng)注釋
?
#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: 采用左孩子，右兄弟的結(jié)構(gòu)實(shí)現(xiàn)AC自動(dòng)機(jī),母串前進(jìn)的過(guò)程仍需采用
回溯的方法找到下一個(gè)匹配點(diǎn), trie圖是不需要回溯的
/* first - 當(dāng)前節(jié)點(diǎn)的第一個(gè)孩子節(jié)點(diǎn)
/* next - 當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)
/* suffix - 后綴節(jié)點(diǎn)
/* queue - BFS 過(guò)程存儲(chǔ)節(jié)點(diǎn)
/* id - 該危險(xiǎn)節(jié)點(diǎn)所對(duì)應(yīng)的單詞，0表示其為安全節(jié)點(diǎn)
/* place - 單詞所對(duì)應(yīng)的危險(xiǎn)節(jié)點(diǎn)編號(hào)
/* node - trie圖節(jié)點(diǎn)的存儲(chǔ)
/* letter - 當(dāng)前字典樹(shù)插入的單詞
/* 其他(略)
/***********************************************************************
*/
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個(gè)方向，方向均為反方向，便于找到初始點(diǎn)位置
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)
//
字典樹(shù)中插入第n個(gè)單詞
{
int
p
=
0
, t;
for
(
int
i
=
strlen(letter)
-
1
; i
>=
0
; i
--
)
//
從后往前插入，便于找到初始點(diǎn)
{
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];
//
如果當(dāng)前節(jié)點(diǎn)不存在c孩子，則到后綴結(jié)點(diǎn)中尋找
}
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]]])
//
如果后綴結(jié)點(diǎn)是危險(xiǎn)節(jié)點(diǎn)，則該節(jié)點(diǎn)也是危險(xiǎn)節(jié)點(diǎn)
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
;
}
?
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
