'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List
import collections

class Solution:
    # https://leetcode.com/problems/image-overlap/discuss/150504/Python-Easy-Logic
    def largestOverlap1(self, A: List[List[int]], B: List[List[int]]) -> int:
        d = collections.defaultdict(int)
        a = []
        b = []
        for i in range(len(A)):
            for j in range(len(A[0])):
                if(A[i][j] == 1):
                    a.append((i,j))
                if(B[i][j] == 1):
                    b.append((i,j))
        ans = 0
        for t1 in a:
            for t2 in b:
                t3 = (t2[0]-t1[0],t2[1]-t1[1]) # the translation/vector 
                # connecting two 1 points in two matrixes
                d[t3] += 1
                # the one transition making the most overlapping 1s
                ans = max(ans, d[t3]) 
        return ans
    
        
        
    # brutal force
    # T: O(N^4); S: O(1)
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        
        def overlap_ct(x_shift, y_shift, m1, m2):
            # m1 is the matrix to be shifted, m2 is the other one
            n = len(m1); ct = 0
            # x_shift: the columns are changing
            # row2, row1 is because row2 starts from 0
            # we only need to consider rows remained after shifting, since
            # new rows will be all zeros
            for row2, row1 in enumerate(range(y_shift, n)):
                for col2, col1 in enumerate(range(x_shift, n)):
                    if m1[row1][col1] == m2[row2][col2] == 1:
                        ct += 1
            return ct
        
        
        if not A or not B: return 0
        n = len(A)
        max_overlaps = 0
        for x_shift in range(n): # we only consider positive here, since
            # all the negative cases are considered by moving another matrix
            for y_shift in range(n):
                max_overlaps = max(max_overlaps, \
                                   overlap_ct(x_shift, y_shift, A, B))
                max_overlaps = max(max_overlaps, \
                                   overlap_ct(x_shift, y_shift, B, A))
        return max_overlaps
                
                
                
                
            