首先考慮這個子問題：
從地圖上的某一點開始一直向右上方發(fā)展，一共能組成多少個以這個點的字母為開頭的單詞。
那么要把以這個點為左下角的矩形中的點全部都考察一遍。
假設這個點的字母為'N'，那就要看所有單詞組成的單詞樹里面，所有'N'節(jié)點孩子的字母，是否出現(xiàn)在這個矩形中。
如果有出現(xiàn)的話，則又是一個子問題了。
把所有這樣的子問題的和求出來，就是答案了。
再考慮一個細節(jié)：
'N'節(jié)點在單詞樹中可以出現(xiàn)很多次，因此每個'N'節(jié)點都是一個子問題。表示：
所有組成的單詞，第一個字母節(jié)點是'N'，余下的字母節(jié)點出現(xiàn)的'N'的子樹里。
動態(tài)規(guī)劃的時候，對于每個節(jié)點要處理一次，因為每個節(jié)點的孩子都不一樣。
在矩形中統(tǒng)計所有孩子對應的子問題的和。
關鍵是怎么存放子問題的答案：
我們需要找出矩形中跟指定孩子對應的點。如果把答案存放在地圖W*H的數(shù)組里面，那就比較麻煩，需要枚舉。
但是如果存放在單詞樹里面，就好很多。
如果我們從上往下掃描每一行，每一行從右到左掃描。那就只需要存放長度為W的一維數(shù)組了。
考慮一個細節(jié)：
對于地圖上的點'N'，要以什么樣的順序處理單詞樹的每個'N'。
按照單詞樹的位置，應該從上到下處理。
代碼寫出來，跑了100ms+，居然排到第9，然后換了gcc編譯，又排前了一點！
發(fā)現(xiàn)前面的人，除了第二名，估計算法都是一樣的。
#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;
}