Salve a tutti,
Ho un problema che non riesco a risolvere, o meglio non riesco ad implementare.
Il problema è il seguente:

data ad esempio la matrice:

....0 1 2 3
0 * * * -
1 * - * *
2 * - - -
3 * - * *

Dovrei trovare l' accoppiamento MINIMO tra asterischi adiacenti.
In questo caso il risultato dovrebbe essere 5 ovvero gli accoppiamenti A={(00-10),(01-02),(12-13),(20-30),(32-33)}
nel caso in cui non ci sia un accoppiamento perfetto il singolo * che rimane solo/i vengono contati come singoli appunto.
Penso sia appunto un problema di copertura degli spigoli, magari gestito con un grafo dove si hanno archi e vertici, con backtraking, solo che non capisco come impostarlo...

qualsiasi consiglio è accettato.

Spero di aver formulato bene la domanda, e di non aver violato qualche punto del regolamento, sono nuovo perdonatemi...