from zelle import Zelle

def startzielpaar(l) -> list[Zelle]:

    def dist(a: Zelle, b:Zelle) -> int:
        """Manhattan distance zwischen zwei Zellen"""
        return abs(a.x-b.x)+abs(a.y-b.y)

    # Kandidaten suchen
    randzellen = []
    # Horizontaler Rand durchgehen und Zellen «einsammeln»
    for x in range(l.breite):
        if l[x,0].bild == 0:
            randzellen.append(l[x,0])
        if l[x,l.hoehe-1].bild == 0:
            randzellen.append(l[x,l.hoehe-1])
    # Vertikaler Rand durchgehen (Ecken nicht noch einmal einsammeln)
    for y in range(1,l.hoehe-1):
        pass   # Diese Zeile entfernen, fehlenden Code ergänzen.
        #
        # TODO: Zellen hinzufügen, analog zu horizontalem Rand
        #

    # Paar mit grösser Enfernung suchen
    maxdist = 0
    paar = []
    for i in range(len(randzellen)-1):  # 0 bis anzahl - 2
        for j in range(i+1, len(randzellen)):  # i+1 bis anzahl -1
            d = dist(randzellen[i], randzellen[j])
            #
            # TODO falls d>maxdist, maxdist anpassen
            #      und die Liste paar mit den aktuellen Zellen definieren.
            #

    return paar