a070. 四向水印

題目描述

印刷廠懷疑有些海報藏著特殊水印。你拿到一張字母海報，以及一小塊水印圖樣，要找出海報上有多少個位置符合這個圖樣。水印可以旋轉，因此同一個圖樣可能以不同方向出現在海報上。

一、海報和水印是什麼？

海報是一個 R × C 的長方形方格，共有 R 列（由上往下），每列有 C 格（由左往右）。每格都是一個大寫英文字母。

水印也是長方形方格，原本共有 H 列、每列 W 格。水印中的字元有兩種：

• 大寫英文字母：海報上對應的那一格必須是相同字母。
• ?：萬用格，可以對應任意一個字母。每個 ? 都獨立比對，不同的 ? 不必對應相同字母。

例如，水印是：

A?
DE

海報上的一塊區域若是 AB / DE 或 AZ / DE（/ 表示換列），都能符合這個方向的水印；若是 AB / DF 就不符合，因為右下角必須是 E，不能是 F。? 仍然占一格，不能省略那一格，也不能一次對應多個字母。

二、水印可以怎麼旋轉？

你可以將整塊水印順時針旋轉 0°、90°、180° 或 270°，再拿去比對海報。0° 就是保持原樣；所有字母和 ? 都要一起移到旋轉後的位置。只能旋轉，不能另外做左右或上下鏡像翻轉。

例如，原本的水印有 2 列、每列 3 格，四個方向分別是：

0°：
A?C
DEF

90°：
DA
E?
FC

180°：
FED
C?A

270°：
CF
?E
AD

旋轉 0° 或 180° 後，尺寸仍是 H × W；旋轉 90° 或 270° 後，尺寸會變成 W × H。上例的水印便會從「2 列、每列 3 格」變成「3 列、每列 2 格」。

三、怎樣才算一個符合的位置？

先選定海報上的一格 (r, c)，把旋轉後水印的左上角對準這一格，再逐格比對。這裡的列號與格子位置都從 1 開始，(1, 1) 就是海報最左上角。

某個方向要符合，必須同時滿足：

1. 整塊水印都放得進海報，不能有任何一格超出邊界，就算超出去的是 ? 也不行。
2. 水印中每個大寫字母，都與海報上相對位置的字母相同。
3. 水印中的 ? 可以對應海報上的任意字母。

例如，上面的水印 A?C / DEF，可以旋轉 90° 後，與下面這張海報完全吻合：

DA
EB
FC

此時左上角是 (1, 1)，水印的 ? 對應海報上的 B。原方向有 3 格寬，放不進這張只有 2 格寬的海報，但旋轉後可以。因此，某個方向放不下，不代表其他方向也放不下。

四、最後要算什麼？

請計算符合條件的不同左上角位置數。對同一個 (r, c)，四個方向中只要有至少一個符合，這個位置就算 1 次；即使有兩個或四個方向都符合，也只能算 1 次。

不同左上角的位置要分別計算，即使它們覆蓋的區域互相重疊也可以。每次比對都是使用原本的海報，不會真的蓋章、修改字母或占用格子。若整張海報沒有任何位置能符合，答案就是 0。

輸入格式

輸入依序包含以下內容：

1. 第一行有兩個整數 R C，以空白分隔，表示海報有 R 列、每列 C 格。
2. 接下來 R 行描述海報，每行恰有 C 個大寫英文字母，字母之間沒有空白。
3. 下一行有兩個整數 H W，以空白分隔，表示旋轉前的水印有 H 列、每列 W 格。
4. 接下來 H 行描述水印，每行恰有 W 個字元，只包含大寫英文字母與 ?，字元之間沒有空白。

海報與水印都按照由上往下的順序輸入，每行字元則由左往右排列。

限制

• 1 ≤ R, C ≤ 60；1 ≤ H, W ≤ 10
• 海報只含大寫英文字母；水印只含大寫英文字母與 ?

輸出格式

輸出一個整數，表示至少有一個旋轉方向能符合水印的不同左上角位置數，並換行。只需輸出數量，不需要輸出位置或旋轉角度。

範例1

範例輸入：

3 3
ABC
DEF
GHI
2 2
AB
DE

範例輸出：

1

海報有 3 列、每列 3 格，水印有 2 列、每列 2 格。水印不旋轉，左上角對準 (1, 1) 時，對應區域的第一列是 AB、第二列是 DE，四格全部吻合。

能完整放下水印的左上角共有 (1, 1)、(1, 2)、(2, 1)、(2, 2) 四個位置；後三個位置無論使用哪個旋轉方向都不符合。其他位置則會超出邊界。因此只有一個符合的位置，輸出 1。

範例2

範例輸入：

2 2
AA
AA
1 1
?

範例輸出：

4

水印只有一格，而且是 ?，所以可以對應海報上任意一格的 A。四個符合的左上角位置為 (1, 1)、(1, 2)、(2, 1)、(2, 2)。

這塊水印旋轉後仍然是 ?，每個位置都能用四種角度符合，但每個位置只算一次。因此答案是 4，不是 16。