Suddivisione di un'area rappresentata come matrice

[provola-votailprof]

Salve a tutti!
Sono nuovo da queste parti e non sono neanche molto sicuro che questa sia la sezione giusta in cui discutere di questo problema.
Sono uno studente di ingegneria informatica e sto cercando di scrivere un programma in cui è necessario suddividere un'area rappresentata come una matrice in n regioni tutte confinanti fra loro (se è possibile, ovviamente). Non importano le dimensioni di ciascuna regione, la cosa importante è che ciascuna confini con le altre. Esempio:

matrice 3x4, ciascuna regione è identificata da un numero.
111
112
122
333

Non è un esercizio che è stato proposto, mi è solo venuto in mente e stavo tentando di risolverlo. Tempo fa ho studiato programmazione matematica (a.k.a. ricerca operativa) e ricordo un discorso del professore su qualcosa del genere, ma l'informazione si è persa nei miei ricordi per cui perdonate la povertà di linguaggio matematico!
Qulacuno può indirizzarmi nella modellizzazione del problema?
Vi ringrazio in anticipo,
ZaC

[apatriarca]

Non mi è del tutto chiaro in che modo dovrebbe presentarsi l'input e l'output di questo programma. Puoi dare maggiori dettagli? Algoritmi di questo tipo sono comunque utilizzati comunemente nell'elaborazione delle immagini (per esempio quando si vogliono estrarre degli elementi da un immagine). Mi viene comunque difficile indirizzarti verso qualche tecnica senza avere ben presente in che modo le varie regioni sono rappresentate nella tua matrice di input.

[provola-votailprof]

Gli unici dati in input sono: il numero di righe e di colonne che compongono la matrice ed il numero di zone. L'output dovrebbe essere la matrice ripartita in modo che tutte le aree siano confinanti fra loro oppure l'assenza di soluzione per i dati inseriti.
Ad es. una matrice 2*2 e 4 zone non ha soluzione.
1 2
3 4
Un confine in diagonale non è un confine

[apatriarca]

A quanto pare non avevo capito molto del problema... Ci devo pensare anche se secondo me si tratta di un problema abbastanza complicato da risolvere. Le regioni devono essere connesse (cioè formate da un solo blocco)?

[provola-votailprof]

Sì.
Grazie per l'attenzione ti ripeto è solo un mio esercizio, mentale ed informatico... Ci ho speso l'intera giornata ma non sono arrivato a nessuna conclusione :/

[apatriarca]

Essendo più che altro interessato agli aspetti teorici (anche se in effetti sono partito da ingegneria) più che altro sono interessato alla domanda: è possibile suddividere un quadrato in N regioni piane tutte confinanti?

[provola-votailprof]

Può anche essere un rettangolo. Comunque, è la stessa domanda che mi sono posto anch'io... Ho fatto un paio di schizzi qua e là e spesso ho trovato una soluzione, ma non riesco a dare una forma matematica al quesito :/

PS: studio a Torino

[apatriarca]

Sono arrivato alla conclusione che non è possibile avere più di 4 regioni connesse tutte tra loro confinanti. Sarebbe infatti in contraddizione con il famoso teorema dei quattro colori. Per colorare una mappa di questo tipo sarebbe infatti necessario usare più di quattro colori ma il teorema afferma che quattro sono sempre sufficienti. Quindi puoi limitarti al caso di 3 o 4 regioni piane. che si possono generare abbastanza facilmente.

[provola-votailprof]

Oh grandioso!!! Era proprio questo il mio ricordo della lezione di ricerca operativa!!!! Fantastico!!! Infatti con 5 regioni non ero riuscito a fare un disegno che soddisfacesse la richiesta!!!
Resta comunque il dubbio sull'implementazione di un algoritmo del genere, ci penserò e se avrò problemi... domanderò
Grazie ancora.

[adaBTTLS1]

una cosa del genere può andar bene?

1111
3224
3224
3344

[apatriarca]

Con quattro il meglio che ho trovato è questo. Non credo sia possibile ridursi a dimensioni inferiori ma a dimensioni maggiori è sempre possibile.

1 1 1
2 3 4
2 4 4