Otto Regine
Avete a disposizione una scacchiera di dimensioni 8×8. Il vostro obiettivo è collocare otto regine sulla scacchiera in modo che nessuna regina attacchi un’altra. Due regine si dicono in conflitto se si trovano sulla stessa riga, colonna o diagonale. La scacchiera contiene caselle libere (
.) e caselle riservate (*), e potete posizionare le regine esclusivamente sulle caselle libere. Tuttavia, le caselle riservate non impediscono alle regine di attaccarsi a vicenda.Stabilite il numero totale di configurazioni con cui è possibile sistemare le otto regine senza che alcuna di esse possa attaccarne un’altra.
Input
L’input è composto da otto righe, ognuna delle quali contiene otto caratteri. Ogni carattere corrisponde a una casella della scacchiera. Un punto (
.) indica una casella libera, mentre un asterisco (*) indica una casella riservata.Output
Stampate un singolo numero intero, corrispondente al totale dei modi in cui è possibile disporre le otto regine senza che due di esse possano attaccarsi.
Esempi
Input | Output |
........
........
..*.....
........
......*.
........
...*....
........ | 72 |
........
........
.......
........
........
.....**.
.......
........ | 65 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB