algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

image-overlap.py (892B)

      1 class Solution:
      2 
      3     def safe_read(self,img1,x,y):
      4         if y >= len(img1) or x >= len(img1[y]) or x < 0 or y < 0:
      5             return 0
      6         return img1[y][x] 
      7 
      8     # we shift img1
      9     def shift_and_check(self,img1,img2,shift_x,shift_y):        
     10         count = 0
     11         for y in range(len(img2)):
     12             for x in range(len(img2[y])):
     13                 if img2[y][x] == 1:
     14                     if self.safe_read(img1,x-shift_x, y-shift_y):
     15                         count += 1
     16         return count
     17 
     18     def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
     19         best = 0
     20 
     21         for y in range(len(img1)):
     22             for mult_y in [-1,1]:
     23                 for x in range(len(img1[y])):
     24                     for mult_x in [-1,1]:
     25                         best = max(self.shift_and_check(img1,img2,x*mult_x,y*mult_y), best)
     26                 
     27         return best