ciao a tutti, sono nuovo quindi perdonatemi se sbagli qualcosa
Vi pongo subito il mio problema:
Allora data una matrice M. Ogni cella della matrice può essere
vuota oppure contenere un soldato (alleato o non).
Un soldato controlla un altro(o più) soldato se quest'ultimo si trova nella cella a sinistra, destra,
sopra, sotto o in una delle diagonali.
Se il soldato controllato è un alleato, lo aiuta, altrimenti
lo combatte. Inoltre, un soldato controlla sempre se stesso.
Per ogni soldato alleato si conosce il suo livello di potenza.
L'obiettivo per vincere la battaglia è quello di trovare un gruppo di soldati alleati che siano
abbastanza forti da superare una certa soglia di potenza e che riescano a controllare tutti gli
altri soldati (alleati e non) sul campo di battaglia. Inoltre, si vuole salvare più vite possibili,
quindi questo gruppo deve essere formato dal numero minimo di soldati alleati possibile.
Quindi letta da input la matrice M rappresentante il campo di battaglia e una soglia di potenza t, selezioni un
gruppo di soldati alleati X tale che:
- il livello di potenza totale del gruppo sia maggiore o uguale ad una data soglia t, dove il
livello di potenza totale del gruppo è dato dalla somma di tutti i livelli di potenza dei
soldati appartenenti al gruppo;
- il gruppo scelto deve controllare tutti gli altri soldati sul campo di battaglia, ovvero non
può esserci un soldato (alleato o non) che non sia controllato da qualche altro soldato, e
- il numero di soldati alleati che compone il gruppo X deve essere il minimo possibile.
La richiesta è quella di scegliere i soldati alleati più forti per controllare tutto il
campo di battaglia, utilizzando le informazioni a sua disposizione.
Il programma deve restituire il numero di soldati alleati n che compongono X.
ESEMPIO INPUT
//righe, colonne , potenza da superare, numero soldati a disposizione
3 8 42 5
//SOLDATI A DISPOSIZIONE
sa 13 (1,2)
sb 8 (1,0)
sc 34 (2,1)
sd 3 (1,5)
se 21 (2,5)
//CAMPO DI BATTAGLIA
. . * . . * . .
* . * * . * * .
. * . . . * . .
//RISULTATO
result
3