a069. 同步文字校對

題目描述

出版社員把兩張透明投影片 A、B 上的文字印得有點錯位。每張投影片都是由大寫字母與透明格 . 組成的方格；你可以拿起 B，在不旋轉、不翻面的情況下，把它平移到 A 的上方，看看兩張投影片的文字能重合多少。

以 A 的左上角為座標 (0, 0)。若 B 左上角放在 (dy, dx)，dy 為向下移動的列數，dx 為向右移動的行數；往上或往左可用負數。只有兩張投影片的矩形範圍都涵蓋到的格子才可能得分：兩個位置都是相同的大寫字母，該格得 1 分；不同字母或任一方為 .，得 0 分。

只比較兩張矩形範圍至少重疊一格的放法。請找出最高總分和對應的位移；最高分若有多種放法，選 dy 最小的，再從中選 dx 最小的。即使所有放法的得分都是 0，也仍要依這套規則選出一種位移。

輸入格式

第一行 R1 C1，接著 R1 行 A；下一行 R2 C2，接著 R2 行 B。

限制

• 1 ≤ R1, C1, R2, C2 ≤ 12
• 每格是大寫英文字母或 .；座標以 0 起算，向下、向右為正

輸出格式

輸出一行 最大吻合數 dy dx。

範例1

範例輸入：

2 2
AB
CD
2 2
AB
CD

範例輸出：

4 0 0

兩張投影片完全重合時，四個字母都對齊，不需要平移。

範例2

範例輸入：

1 2
AB
1 2
BA

範例輸出：

1 0 -1

往左或往右錯開一格都吻合一次，選 dx 較小的 -1。