Walk the Talk (PKU 3043)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3043

問題

H*Wのグリッド上に文字が書かれている。グリッドの上では左と下には行けず、右や上の方にいく場合は何マスでもジャンプできる。このグリッド上で辞書に載っている単語を作るパスは何通りあるか？
1<=H,W<=30
単語の長さ<=4

解法

DPで解く。
DP[y][x][index]は座標(x,y)でindex番目の単語のsufixの作り方は何通りあるかをあらわす。DP[y][x][index]はそのすぐ右、上、右上の座標を見れば更新できる。
全体としてはO(3000HW)くらいになる(sufixは3000個くらい存在する)。
stlのmapを使うと間に合わないのでsufixは数値にして配列を使って変換した。