Catena di secchi#10316
In una fattoria è scoppiato un incendio e le mucche si affrettano a spegnerlo! La fattoria è rappresentata da una griglia di simboli di dimensione 10 \times 10 come segue:
..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........Il simbolo indica il fienile, che ha appena preso fuoco. Il simbolo indica il lago, mentre indica la posizione di un grosso masso.
Le mucche vogliono organizzare una "catena di secchi" (bucket brigade), disponendosi lungo un percorso tra il lago e il fienile, per passarsi i secchi d'acqua lungo la catena e aiutare a spegnere l'incendio. Un secchio può essere passato da una mucca a un'altra se le due mucche si trovano immediatamente adiacenti l'una all'altra in una delle quattro direzioni: nord, sud, est oppure ovest.
Allo stesso modo, una mucca può riempire un secchio d'acqua dal lago solo se si trova immediatamente adiacente al lago. Una mucca può gettare un secchio d'acqua nel fienile solo se si trova immediatamente adiacente al fienile.
Determinare il numero minimo di celle "" che devono essere occupate dalle mucche per organizzare una catena funzionante per il passaggio dei secchi.
Una mucca non può trovarsi su una cella occupata dal grosso masso. È garantito che il fienile e il lago non siano immediatamente adiacenti l'uno all'altro.
È composto da righe, ciascuna contenente simboli che descrivono la disposizione degli oggetti nella fattoria.
Stampare un singolo numero intero: il numero minimo di mucche necessarie per organizzare una catena funzionante per il passaggio dei secchi.
Di seguito è mostrata una delle possibili disposizioni che utilizza il numero ottimale di mucche — :
..........
..........
..........
..B.......
..C.......
..CC.R....
...CCC....
.....C....
.....L....
..........Esempio 1