Jakiej powierzchni będzie największy możliwy kształt po połączeniu prostokątów

Mamy kwadrat n x n podzielony na bloki 1x1. Każdy blok może być zamalowany lub niezamalowany. Na początku zamalowane bloki tworzą jedynie większe prostokąty.
Mamy zamalować 2 bloki, tak aby powstał największy możliwy zamalowany spójny kształt. Kształt ten nie musi już być prostokątem. Jeżeli 2 bloki stykają się bokami - są połączone, jeżeli stykają się jedynie narożnikami - nie są połączone i tworzą odrębne kształty.
Jaki byłby najbardziej efektywny sposób na znalezenie takiej największej możliwej powierzchni?

EDIT:
W tytule piszę po połączeniu prostokątów, gdyż (o ile jest wolne miejsce na planszy) zawsze możemy dokleić (czyli zamalować) gdzieś obok te nowe bloki, ale to tylko +2. Jeżeli chcemy więcej (a szukamy największej możliwości), to musimy już połączyć jakieś prostokąty.

@Michał Bodziony
Mniej więcej tak. Z tym, że jeden blok może np. połączyć cztery podłużne prostkąty i do tego drugi dla przykładu jeszcze jeden prostokąt.
Na przykład:

00101
00100
11011
00100
00100

00111
00100
11111
00100
00100

Tak. Chodzi jednak o wskazówki, podobne zadania itd. Nikt nie prosi o gotowy kod, czy zaprojektowanie algorytmu.

Najprościej piszesz funkcje przeszukuje plansze BFS i znajduje największy spójnie zamalowany obszar i zapisuje listę pustych punktów. Stosując podwójnego fora sprawdzasz wszystkie możliwe pary do zamalowania swoją funkcją, zapisujesz najlepszy wynik złożoność n^3.
Możesz też wyszukać wszystkie spójne obszary sprawdzić, zapisać je i sprawdzić i zapisać z iloma się łącza w odległości dwóch bloków (np.1001 NIE 10101) i zapisać to jako graf . Znalezienie najlepszej pary w takim grafie można zrobić w czasie liniowym. Stosując programowanie dynamiczne można brakująca cześć zadania zrobić w czasie n. Musisz znaleźć sposób wykrycia wszystkich spójnych obszarów i ich połaczeń za pomocą DFS, a potem napisać to samo za pomocą BFS i zapamiętywać wyniki. Umiem to narysować ale opis mnie przerasta. Jak to zrobisz to zostaje przypadek graniczny że jest tylko jedno połączenie lub nie ma wcale.

topik92 napisał(a):

Najprościej piszesz funkcje przeszukuje plansze BFS i znajduje największy spójnie zamalowany obszar i zapisuje listę pustych punktów. Stosując podwójnego fora sprawdzasz wszystkie możliwe pary do zamalowania swoją funkcją, zapisujesz najlepszy wynik złożoność n^3.

Spójnych prostokątów może być O(n²), więc wszystkich par będzie O(n⁴).