Восемь ферзей
Вам дана шахматная доска размером
8x8. Ваша задача — расставить восемь ферзей на этой доске так, чтобы ни один ферзь не атаковал другой. Два ферзя считаются атакующими друг друга, если они находятся на одной строке, в одном столбце или на одной диагонали. На доске есть свободные клетки (.) и зарезервированные клетки (*); ферзей можно ставить только на свободные клетки. При этом зарезервированные клетки не мешают ферзем угрожать друг другу.Определите, сколько всего существует вариантов расстановки ферзей на доске при условии, что ни один ферзь не атакует другой.
Входные данные
Программа получает на вход восемь строк, в каждой из которых содержится по восемь символов. Каждая строка описывает один ряд доски: точка (
.) означает свободную клетку, а звездочка (*) — зарезервированную клетку.Выходные данные
Выведите одно число — количество различных способов расставить восемь ферзей так, чтобы они не угрожали друг другу.
Примеры
Input | Output |
........
........
..*.....
........
......*.
........
...*....
........ | 72 |
........
........
.......
........
........
.....**.
.......
........ | 65 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB