Quale sarebbe il modo ottimale per risolvere un problema come questo?

3

Ho un problema in cui devo cambiare tutti gli X di un array 2D in 0, e devo calcolare i passi minimi (dove un singolo passo consiste nel cambiare un'intera riga o colonna) richiesto per farlo. Ad esempio, in un array come -

[[X, X, X],

[X, 0, 0],

[X, 0, 0]]

Il numero minimo di passaggi richiesti qui è 2.

Ho pensato ad un approccio a forza bruta (dove sto verificando una riga una volta e in seguito a una colonna e poi confrontandole per verificare quale prende il numero minimo di passaggi) ma questo mi darebbe una risposta di 3, che non è l'output desiderato.

Qualsiasi aiuto o indizio su come dovrei affrontare questo problema sarebbe apprezzato, grazie!

    
posta Tarun Verma 05.10.2013 - 19:27
fonte

2 risposte

1

Se un "passo" sta cambiando una riga o una colonna, allora il tuo obiettivo è fare i cambiamenti che influenzeranno il maggior numero di Xes prima di fare quelli che coprono meno.

Il modo per capirlo è attraversare una volta l'intero array e tenere traccia del numero di Xes in ogni riga e colonna. Per una variante minore dell'esempio, il risultato finale di tale calcolo sarà simile a questo:

   C C C
   1 2 3
R1 X X X -- 3 Total
R2 0 X 0 -- 1 Total
R3 0 X 0 -- 1 Total
   | | |
   1 3 1 Totals

Rompere queste informazioni in una lista (leggi ogni elemento come "3 X nella riga 1", "1 X nella riga 2", ecc.):

3/R1  1/R2  1/R3  1/C1  3/C2  1/C3

Un ordinamento discendente dei conteggi rende abbastanza ovvio quale modificare prima:

3/R1  3/C2  1/R2  1/R3  1/C1  1/C3

Cambia R1, prendi nota di ciò come primo passo e rimuovilo dall'elenco. Quando cambi una riga con Xes, le colonne che contenevano quelle Xes (tutte in questo caso) ora ne contengono una in meno. Ciò significa che devi ridurre il conteggio in ogni colonna in cui hai trovato una X:

0/C1  1/R2  1/R3  2/C2  0/C3

Questo cambiamento fa saltare l'ordinamento direttamente fuori dall'acqua, perché ora l'oggetto che eliminerà il maggior numero di Xes non è più in primo piano. Un nuovo ordinamento risolve il problema e rivela la colonna 2 come passaggio successivo:

2/C2  1/R2  1/R3  0/C1  0/C3

Dopo un cambio, decremento e riordinamento, sei a questo punto:

0/R2  0/R3  0/C1  0/C3

Un primo elemento zero significa che hai raggiunto la fine perché tutto ciò che lo segue sarà anche zero, ovvero non più Xes nell'array. Qualsiasi altra cosa significa che ripeti il processo.

Non solo otterrai il numero di passaggi da questo, ma riceverai anche un elenco di cosa sono quei passaggi.

Anche tu non devi necessariamente fare qualcosa. Puoi semplicemente attraversare l'elenco ogni volta e tenere premuto sull'elemento con il conteggio maggiore. Se stai utilizzando un linguaggio che ha una raccolta ordinata disponibile, scrivilo sarebbe un gioco da ragazzi.

    
risposta data 05.10.2013 - 22:21
fonte
1

Che sembra essere un'intervista e / o una domanda sull'esercizio universitario, quindi ti darò solo alcune indicazioni ...

Immagina che ogni matrice possibile (gli array con X e zero) siano nodi in un grafico. Da ciascun nodo, puoi generare un altro con i passaggi che hai menzionato (cambiare una linea o cambiare una colonna).

Quindi, con:

[[X, X, X],    
[X, 0, 0],    
[X, 0, 0]]

Puoi andare a:

[[0, 0, 0],    
[X, 0, 0],    
[X, 0, 0]]

or

[[0, X, X],    
[0, 0, 0],    
[0, 0, 0]]

or

[[X, X, 0],    
[X, 0, 0],    
[X, 0, 0]]

or

(Goes on...)

Ora dovresti, dalla matrice iniziale, provare a fare una ricerca in ampiezza (vedi questo link wikipedia e / o il tuo libro dell'algoritmo preferito) per una matrice che soddisfi le tue condizioni: tutti gli zeri.

    
risposta data 05.10.2013 - 21:50
fonte

Leggi altre domande sui tag