題目連結:
題目意譯:
你被給定兩張圖面,img1 和 img2,各自以二元、大小為 n × n 的方形矩陣表示。一個二元矩陣只有 0 和 1 這兩種數值。
我們將任意地將所有位元 1 往上下左右各自移動任意單位來移動一張圖片。接著我們將這張圖片疊在另一張上面。然後我們統計兩張圖的同位置同時是位元 1 之位置數量,作為重疊值。
注意到位移不包含任何形式的旋轉。任意移出矩陣範圍外的位元 1 將會被消掉。
回傳最大可能的重疊值。
限制:
n == img1.length == img1[i].length
n == img2.length == img2[i].length
1 ≦ n ≦ 30
img1[i][j] 只會是 0 或是 1。
img2[i][j] 只會是 0 或是 1。
範例測資:
範例 1:
輸入: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
輸出: 3
解釋: 我們將 img1 往右位移 1 單位以及往下位移 1 單位。
在兩張圖片同時是 1 的位置數量為 3(以紅色標示)。
範例 2:
輸入: img1 = [[1]], img2 = [[1]]
輸出: 1
範例 3:
輸入: img1 = [[0]], img2 = [[0]]
輸出: 0
解題思維:
就單純地窮舉所有可能的位移即可,以 img1 的左上角為例,則我們有 n × n 個位置可以放這個左上角。而這樣我們還會錯過一些重疊位置,因為還有左上角超出位置的方式。而我們可以利用相同的方式來窮舉右上角、左下角和右下角。
因此就單純地對於每個可能的位置去計算重疊值(當然,要忽略超出範圍的索引值),然後取最大值即可。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。