a078. 錯位的照片

題目描述

兩張灰階照片 A 與 B 都有 R 行、C 列，像素值是 0 到 255 的整數。拍攝時兩張照片可能錯開一點；你可以把 B 相對於 A 平移 (dr, dc) 來比對。dr 是向下移動的格數，dc 是向右移動的格數；負數表示向上或向左。兩者各只能取 -1、0、1，因此總共只有九種平移方式。不能旋轉或翻面。

對於 A[r][c]，平移後要比較的位置是 B[r+dr][c+dc]。只有兩個座標都在 B 的範圍內時才比較，而且像素值相同才得到 1 個配對；超出照片範圍的格子不算配對，也不扣分。九種平移方式都要考慮，即使照片只有一行或一列也一樣。

找出配對數最多的方式。若多種方式並列，先選 |dr|+|dc| 較小的；若仍相同，選 dr 較小的；若仍相同，選 dc 較小的。即使沒有任何像素相同，也要依這套規則輸出一種位移。

規則圖解

用 A 的格子當作基準，九種平移都是找 B 的對應格，而不是把照片裁成新的尺寸。候選位移如下：

dr ＼ dc	-1（往左）	0	+1（往右）
-1（往上）	(-1, -1)	(-1, 0)	(-1, 1)
0	(0, -1)	(0, 0)	(0, 1)
+1（往下）	(1, -1)	(1, 0)	(1, 1)

以範例一的 (dr, dc)=(0, 1) 為例：

A                   B
1   2   3           9   1   2
4   5   6           9   4   5

A[0][0]=1 ↔ B[0][1]=1    A[0][1]=2 ↔ B[0][2]=2
A[1][0]=4 ↔ B[1][1]=4    A[1][1]=5 ↔ B[1][2]=5
A[0][2]、A[1][2] 對應到 B 的第 3 列，已出界

因此這種位移得到 4 個配對。出界的兩格不會拿來比較；即使某種位移完全沒有重疊，它的得分也只是 0。平手時依序比較：配對數多 → |dr|+|dc| 小 → dr 小 → dc 小。

輸入格式

第一行為 R C，兩張照片共同的行數與列數。

接下來 R 行為 A，再接 R 行為 B；每一行依序提供 C 個以空白分隔的整數像素。兩張照片都按從上到下、從左到右輸入，座標從左上角 (0, 0) 起算。

限制

1 ≤ R, C ≤ 200；0 ≤ 像素值 ≤ 255。

輸出格式

輸出一行：最多配對數 dr dc。dr 與 dc 必須都是 -1、0、1 中的整數；配對數是相等的像素格數，不是百分比。

範例1

範例輸入：

2 3
1 2 3
4 5 6
9 1 2
9 4 5

範例輸出：

4 0 1

B 相對 A 向右錯開一格時，兩行各有兩個像素相同。

範例2

範例輸入：

1 1
7
8

範例輸出：

0 0 0

所有方式的配對數都是 0；不移動的曼哈頓距離最小。