a065. 八方向尋字

題目描述

社團的尋字遊戲把字母寫進方格，請同學找出指定單字。單字可以由左往右、由右往左、由上往下、由下往上，也可以沿著四個斜角方向出現，總共八個方向。每次尋找都從某個方格當作第一個字母開始，接著沿固定方向前進。

往前走時每一步只能移到那個方向的下一格，每格取一個字母；途中不能轉彎、跳格、繞到另一側，或走出方格。若取得的字母依序恰好等於目標單字，就找到一次。只要起點不同或方向不同，便視為不同的出現方式，即使選到的部分格子相同也一樣。

例如在整張都是 A 的 2×2 方格尋找 AA，每個角落都有三個能走到另一格的方向，因此總共有 12 次。注意：你只需要比對輸入的單字；若它剛好前後相同，也照起點和方向分開計數，不要自行排除反向走法。

輸入格式

第一行 R C，接著 R 行字母方格；最後一行為目標單字 s。

限制

• 1 ≤ R, C ≤ 30；2 ≤ s 長度 ≤ 30
• 方格與 s 只包含大寫英文字母

輸出格式

輸出一個整數，符合的起點與方向組合數。

範例1

範例輸入：

3 3
CAT
AXA
TAC
CAT

範例輸出：

4

可以從第一列由左往右、第一行由上往下、第三列由右往左，以及第三行由下往上讀到 CAT。

範例2

範例輸入：

2 2
AA
AA
AA

範例輸出：

12

四個格子各有三個可走到相鄰格子的方向。