Pobles d'un país P95415

Considereu un país modelitzat amb una graella amb $c$ columnes i $f$ files. La cantonada superior esquerra es correspon a la posició $(1, 1)$, i la inferior dreta a la $(c, f)$. En aquest país hi ha $n$ cases, totes en posicions enteres. Per defecte, les cases formen part de pobles diferents. Tanmateix, cada casa ha de pertànyer al mateix poble que qualsevol altra casa que es trobi immediatament a la seva esquerra, dreta, a sobre o a sota. Podeu pintar quins són els pobles d’aquest país?

Entrada

L’entrada consisteix en $c$, $f$ i $n$, seguits d’$n$ parells diferents $(x, y)$, amb $1 \le x \le c$ i $1 \le y \le f$, indicant les cases del país. Suposeu que $c$ i $f$ estan entre 1 i 40, i $1 \le n \le f \cdot c$. Cap dels pobles tindrà més de 900 cases.

Sortida

Cal generar una imatge $(15c, 15f)$ de color de fons ‘Beige’. Marqueu les cases amb cercles de diàmetre 5 centrats al quadrat $15 \times 15$ corresponent. Totes les cases de cada poble s’han de pintar del mateix color.

Per decidir el color de cada poble, suposeu que l’ajuntament n’és la casa més amunt (i en cas d’empat, la més a l’esquerra). Ordeneu els pobles entre si segons la posició dels ajuntaments usant el mateix criteri: primer el poble que té l’ajuntament més amunt, i en cas d’empat el que el té més a l’esquerra. Finalment, useu els colors ‘Red’, ‘Green’ i ‘Blue’ en aquest ordre i de forma cíclica per pintar els pobles.

Addicionalment, pinteu la relació d’adjacència entre dues cases d’un poble de color col, situades en els punts (x1, y1) i (x2, y2) de la imatge, fent servir la comanda

dib.line([(x1, y1), (x2, y2)], col)

Observació

Podeu obtenir 40 punts amb casos amb un únic poble (vermell), i on $c$ i $f$ estan entre 1 i 10, com l’Exemple d’entrada 1.