def stej(bitna_slika, a, b, c, d):
    """
    Vrni število ničel in enic v podmatriki.
    """
    st_nicel, st_enic = 0, 0
    for i in range(a, b):
        for j in range(c, d):
            if bitna_slika[i][j] == '0':
                st_nicel += 1
            else:
                st_enic += 1
    return st_nicel, st_enic

def kodiraj(bitna_slika, a=0, b=None, c=0, d=None):
    if b is None:
        b = len(bitna_slika)
    if b <= a:
        return ''
    if d is None:
        d = len(bitna_slika[0])
    if d <= c:
        return ''
    st_nicel, st_enic = stej(bitna_slika, a, b, c, d)
    if st_nicel == 0:
        return '1'
    if st_enic == 0:
        return '0'
    ab_mid = (a + b + 1) // 2
    cd_mid = (c + d + 1) // 2
    return 'D' + kodiraj(bitna_slika, a, ab_mid, c, cd_mid) + kodiraj(bitna_slika, a, ab_mid, cd_mid, d) + \
        kodiraj(bitna_slika, ab_mid, b, c, cd_mid) + kodiraj(bitna_slika, ab_mid, b, cd_mid, d)


def kodiraj(bitna_slika):
    if len(bitna_slika) == 0:
        return ''
    elif all('1' not in i for i in bitna_slika):
        return '0'
    elif all('0' not in i for i in bitna_slika):
        return '1'

    def razbij(bitna_slika):
        x = (len(bitna_slika) + 1) // 2
        y = (len(bitna_slika[0]) + 1) // 2

        return 'D' + kodiraj([bitna_slika[i][:y] for i in range(0,x)]) + kodiraj([bitna_slika[i][y:len(bitna_slika)+1] for i in range(0,x)]) + kodiraj([bitna_slika[i][0:y] for i in range(x,len(bitna_slika))]) + kodiraj([bitna_slika[i][y:len(bitna_slika)+1] for i in range(x,len(bitna_slika))])

    return razbij(bitna_slika)