Eine andere Möglichkeit wäre
floodfill. Wenn die gesuchten Rechtecke - was ich vermute - paraxial sind, ist es sogar nochmal einfacher. Paraxial bedeutet, dass die Seiten eines Rechtecks parallel zu den Achsen des Koordinatensystems liegen.
Das Vorgehen wäre dann ungefähr so:
Finde mittels floodfill jeden zusammenhängenden Bereich von 1en. Falls ein Bereich eine "Insel" aus 0en enthält, ignoriere den Bereich. Andernfalls bilde um den Bereich eine
Minimum Bounding Box. Ist die Boundingbox kleiner als die gewünschte Rechtecks-Mindestgröße, ignoriere den Bereich ebenfalls. Andernfalls, wenn der Bereich und die Boundingbox identisch sind, dann ist der Bereich ein passendes Rechteck. Ob ein Bereich von 1en ohne 0er-Inseln mit einerm gegebenen Rechteck (der Boundingbox) identisch ist kann man testen, indem man innen entlang der Kanten der Boundingbox testet, ob jedes Feld dort eine 1 beinhaltet. Alle noch weiter innen liegenden Felder müssen, da wir 0er-Inseln ja bereits ausgeschlossen haben, ebenfalls 1en sein.
Übrigens: wenn man sich merkt, welche Felder man bereits verarbeitet hat, liegt die Laufzeitkomplexität bei O(n), ebenso wie die Speicherplatzkomplexität.
In specifications, Murphy's Law supersedes Ohm's.
