[Usaco2007 Demo]Walk the Talk

题目描述

Farmer John has set up a puzzle for his cows to solve. At the entrance to the barn, he has laid out an H x W (1 <= 1="" h="" <="30," grid="" of="" letters.="" before="" a="" cow="" can="" enter="" the="" barn,="" she="" must="" spell="" out="" valid="" english="" word="" by="" jumping="" from="" square="" to="" square,="" creating="" sequence="" start="" at="" any="" but="" may="" only="" jump="" subsequent="" that="" is="" located="" right="" and="" or="" above="" current="" (i.e.,="" neither="" left="" nor="" lower).="" next="" be="" distance="" one="" since="" cows="" are="" world-class="" jumpers!="" no="" two="" traverse="" exact="" same="" path,="" although="" allowed="" via="" different="" paths.="" as="" an="" example,="" consider="" this="" (presuming="" 'to'="" 'ox'="" words):="" t="" x="" o="" q="" four="" paths="" valid,="" all="" spelling="" (one="" requires="" 't'="" bottom="" row="" 'o'="" top="" row).="" word,="" would="" require="" 'x'="" 'o',="" which="" not="" allowed.="" given="" list="" words,="" compute="" number="" barn="" without="" repeating="" path.="" file="" `dict.txt'="" will="" available="" contain="" per="" line.="" see="" copy="" it="" http:="" ace.delos.com="" usaco="" dict-twalk.txt="" .="" p="">

---

输入格式

* Line 1: Two integers: H and W * Lines 2..H+1: Each line contains W characters, without spaces, representing a row in the grid. The first row is the top row. The first character in each row is the left-most character.

---

输出格式

* Line 1: The number of cows that can enter the barn without repeating a path.

---

样例输入

3 4
TXXO
TXQT
XTXQ

---

样例输出

4

OUTPUT DETAILS:

4 cows can enter the barn, each one spelling out one of the 'TO's.

---

提示

没有写明提示

---

题目来源

Gold