Quote:
Originariamente inviato da wingman87
Secondo me la cosa migliore è ragionare colonna per colonna: se vuoi fare calcoli sulla zona inferiore parti dal basso e ti fermi quando trovi lo zero, viceversa se vuoi fare calcoli sulla zona superiore parti dall'alto.
L'unico dubbio è: c'è un solo 0 per ogni colonna? Dalla traccia non l'ho capito, anche se suppongo di sì perché altrimenti l'esercizio sarebbe molto più complicato.
|
il testo non specifica se sono o meno presenti quindi dobbiamo supporre che ci possano essere degli 0 che non fanno parte della linea di demarcazione.
io procederei nel seguente modo.
mi creerei un vetttore (chiamiamolo POSIZIONE) di n elementi(matrice m*n) in cui vado a salvare l'indice corrispondente allo zero(separatore)di ogni colonna.
Per trovare questo scorriamo la matrice da sinistra a destra e dall'alto al basso
quindi partendo dall'elemento [0,0] vado a cercare il valore 0 supponiamo sia in [0,i], salvo i in Posizione[0]
allora vado a vedere se in [1,i-1],[1,i],[1,i+1] c'è uno 0 se si aggiorno la i a i-1,i,i+1 (in base a dove ho trovato lo 0, e salvo la i in posizione[1] e così via.
Ora supponiamo di essere arrivati all'elemento [n.i] in cui vi è uno 0.
se alla colonna n+1 non ci sono 0 compatibili, bisogna tornare alla colonna n e vedere se oltre allo 0 in [n,i] vi siano altri 0 compatibili con la colonna [n-1].
e si procede a ritroso fino a trovare una colonna che abbia altri 0 compatibili(se arriviamo alla prima colonna ovviamente non controlliamo più a ritroso ma scendiamo a cercare altri 0).
Scusa se sono mooolto poco esaudiente nella spiegazione, ma non per niente non sono un prof.
Cmq spero hai capito cosa voglia dire, in caso contrario stasera(quando finisco i miei studi giornalieri) vedo di imprementare un algoritmo x trovarti gli elementi separatori
PS
come non detto mi sono accarto di essere completamente perso su diversi argomenti, quindi considerando che ho l'esame giovedì, mi devo mettere a fare le nottate.
se non hai premura provo a scrivere qualcosa venerdi.