首先考慮這個(gè)子問(wèn)題：
從地圖上的某一點(diǎn)開(kāi)始一直向右上方發(fā)展，一共能組成多少個(gè)以這個(gè)點(diǎn)的字母為開(kāi)頭的單詞。
那么要把以這個(gè)點(diǎn)為左下角的矩形中的點(diǎn)全部都考察一遍。
假設(shè)這個(gè)點(diǎn)的字母為'N'，那就要看所有單詞組成的單詞樹(shù)里面，所有'N'節(jié)點(diǎn)孩子的字母，是否出現(xiàn)在這個(gè)矩形中。
如果有出現(xiàn)的話，則又是一個(gè)子問(wèn)題了。
把所有這樣的子問(wèn)題的和求出來(lái)，就是答案了。
再考慮一個(gè)細(xì)節(jié)：
'N'節(jié)點(diǎn)在單詞樹(shù)中可以出現(xiàn)很多次，因此每個(gè)'N'節(jié)點(diǎn)都是一個(gè)子問(wèn)題。表示：
所有組成的單詞，第一個(gè)字母節(jié)點(diǎn)是'N'，余下的字母節(jié)點(diǎn)出現(xiàn)的'N'的子樹(shù)里。
動(dòng)態(tài)規(guī)劃的時(shí)候，對(duì)于每個(gè)節(jié)點(diǎn)要處理一次，因?yàn)槊總€(gè)節(jié)點(diǎn)的孩子都不一樣。
在矩形中統(tǒng)計(jì)所有孩子對(duì)應(yīng)的子問(wèn)題的和。
關(guān)鍵是怎么存放子問(wèn)題的答案：
我們需要找出矩形中跟指定孩子對(duì)應(yīng)的點(diǎn)。如果把答案存放在地圖W*H的數(shù)組里面，那就比較麻煩，需要枚舉。
但是如果存放在單詞樹(shù)里面，就好很多。
如果我們從上往下掃描每一行，每一行從右到左掃描。那就只需要存放長(zhǎng)度為W的一維數(shù)組了。
考慮一個(gè)細(xì)節(jié)：
對(duì)于地圖上的點(diǎn)'N'，要以什么樣的順序處理單詞樹(shù)的每個(gè)'N'。
按照單詞樹(shù)的位置，應(yīng)該從上到下處理。
代碼寫(xiě)出來(lái)，跑了100ms+，居然排到第9，然后換了gcc編譯，又排前了一點(diǎn)！
發(fā)現(xiàn)前面的人，除了第二名，估計(jì)算法都是一樣的。
#include <stdio.h>
#define SIZE 64
#define QUEUE_SIZE 4096
struct tree_node 
{
int end, dp[SIZE];
struct tree_node *child[26], *next;
};
struct queue_node {
int idx;
struct tree_node *ptr;
};
int H, W;
char map[SIZE][SIZE];
struct tree_node nodes[QUEUE_SIZE], root, *hash[26];
int nodes_cnt;
struct queue_node queue[QUEUE_SIZE];
int tail, head;
inline void bfs()
{
struct tree_node *t;
int i;
head = tail = 0;
queue[tail++].ptr = &root;
while (head != tail) {
t = queue[head++].ptr;
for (i = 0; i < 26; i++) {
if (!t->child[i])
continue;
queue[tail].ptr = t->child[i];
queue[tail].idx = i;
tail++;
}
}
for (tail--; tail >= 1; tail--) {
t = queue[tail].ptr;
i = queue[tail].idx;
t->next = hash[i];
hash[i] = t;
}
}
inline void calc(int y, int x)
{
struct tree_node *t, *c;
int i, j, sum;
for (t = hash[map[y][x] - 'A']; t; t = t->next) {
sum = t->end;
for (i = 0; i < 26; i++) {
c = t->child[i];
if (!c)
continue;
for (j = W - 1; j >= x; j--)
sum += c->dp[j];
}
t->dp[x] += sum;
}
}
int main()
{
int i, j, sum;
char str[64], *s;
struct tree_node *t, **p;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &H, &W);
for (i = 0; i < H; i++)
scanf("%s", map[i]);
while (scanf("%s", str) != EOF) {
t = &root;
for (s = str; *s; s++) {
p = &t->child[*s - 'A'];
if (!*p)
*p = &nodes[nodes_cnt++];
t = *p;
}
t->end++;
}
bfs();
for (i = 0; i < H; i++)
for (j = W - 1; j >= 0; j--)
calc(i, j);
sum = 0;
for (i = 0; i < 26; i++) {
t = root.child[i];
if (!t)
continue;
for (j = 0; j < W; j++)
sum += t->dp[j];
}
printf("%d\n", sum);
return 0;
}