""" Image Smoother - https://leetcode.com/problems/image-smoother

    Given a 2D integer matrix M representing the gray scale of an image, 
    you need to design a smoother to make the gray scale of each cell becomes the 
    average gray scale (rounding down) of all the 8 surrounding cells and itself. 
    If a cell has less than 8 surrounding cells, then use as many as you can.

    Example 1:
    
    Input:
    
    [[1,1,1],
     [1,0,1],
     [1,1,1]]
    
    Output:
    
    [[0, 0, 0],
     [0, 0, 0],
     [0, 0, 0]]
    
    Explanation:
    For the point (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
    For the point (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
    For the point (1,1): floor(8/9) = floor(0.88888889) = 0
    
    Note:
    The value in the given matrix is in the range of [0, 255].
    The length and width of the given matrix are in the range of [1, 150].
"""

class Solution(object):
    def imageSmoother(self, M):
        """
        :type M: List[List[int]]
        :rtype: List[List[int]]
        """
        def get_neighbours(M, r, c):
            total = []
            # top-left
            if r - 1 >= 0 and c - 1 >= 0:
                total.append(M[r-1][c-1])
            # top
            if r-1 >= 0:
                total.append(M[r-1][c])
            # top-right
            if r - 1 >= 0 and c + 1 < len(M[0]):
                total.append(M[r-1][c+1])
            # left
            if c - 1 >= 0:
                total.append(M[r][c-1])
            # right
            if c + 1 < len(M[0]):
                total.append(M[r][c+1])
            # bottom-left
            if r+1 < len(M) and c-1 >= 0:
                total.append(M[r+1][c-1])
            # bottom
            if r+1 < len(M):
                total.append(M[r+1][c])
            if r+1 < len(M) and c + 1 < len(M[0]):
                total.append(M[r+1][c+1])
            
            return total
        
        G = [[0 for i in range(len(M[0]))] for j in range(len(M))]
        
        for i in range(len(M)):
            for j in range(len(M[i])):
                new_point = get_neighbours(M, i, j)
                G[i][j] = (sum(new_point) + M[i][j]) // (len(new_point) + 1)
        return G