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.