Polska kwadratowa

Znajoma namówiła mnie do zamieszczenia poniższego zadania, co czynię z pewną taką wstrzemięźliwością, bo jest ono tzw. optimizerem, czyli dłubaniną dla wybrańców lub dla komputerów. Znajoma zmaga się z nim od pewnego czasu i chciałaby mieć pewność, że osiągnęła najlepszy – w tym przypadku najmniejszy – wynik.

Oto mamy Polskę pokratkowaną, czyli podzieloną na małe kwadraciki, a praktycznie narysowaną z grubsza, czyli z „kanciastymi” granicami, na kartce w kratkę.

Pok_1

Czarne kratki to największe miasta wojewódzkie.
Tę Polskę (całą) należy rozparcelować na kwadraty. Dzielić należy oczywiście tylko wzdłuż oznaczonych linii. A najważniejsze jest to, aby kwadratów było jak najmniej. Miasta powinny się znaleźć poza kwadratami, a więc pozostaną kwadracikami 1×1, ale nie są wliczane do końcowego minimum.

Żeby było ciekawiej i dziwniej dodam, że zadanie pochodzi z łamigłówkowych mistrzostw Francji. Dlaczego Francuzi dzielili Polskę – nie powiem. Nie podam także wyniku znajomej, ale jeśli w komentarzach pojawią się gorsze, czyli większe rozwiązania (wystarczy podać liczbę kwadratów), będę je uwalniał bezzwłocznie.

Kom