首先考虑这个子问题：
从地图上的某一点开始一直向右上方发展，一共能组成多少个以这个点的字母为开头的单词。
那么要把以这个点为左下角的矩形中的点全部都考察一遍。
假设这个点的字母为'N'，那就要看所有单词组成的单词树里面，所有'N'节点孩子的字母，是否出现在这个矩形中。
如果有出现的话，则又是一个子问题了。
把所有这样的子问题的和求出来，就是答案了。
再考虑一个细节：
'N'节点在单词树中可以出现很多次，因此每个'N'节点都是一个子问题。表示：
所有组成的单词，第一个字母节点是'N'，余下的字母节点出现的'N'的子树里。
动态规划的时候，对于每个节点要处理一次，因为每个节点的孩子都不一样。
在矩形中统计所有孩子对应的子问题的和。
关键是怎么存放子问题的答案：
我们需要找出矩形中跟指定孩子对应的点。如果把答案存放在地图W*H的数组里面，那就比较麻烦，需要枚举。
但是如果存放在单词树里面，就好很多。
如果我们从上往下扫描每一行，每一行从右到左扫描。那就只需要存放长度为W的一维数组了。
考虑一个细节：
对于地图上的点'N'，要以什么样的顺序处理单词树的每个'N'。
按照单词树的位置，应该从上到下处理。
代码写出来，跑了100ms+，居然排到第9，然后换了gcc编译，又排前了一点！
发现前面的人，除了第二名，估计算法都是一样的。
#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;
}