在一个 棋盘中放置两个皇后,使得它们可以相互攻击,求方案总数.
UVa 11538
两个皇后可以互相攻击,当且仅当它们在"同一行"或"同一列"或"同一对角线".这三种情况互相独立,可以用加法原理.
推广到多行的情况,每一行的情况互不影响,可以用加法原理,即:
"同一列"和"同一行"原理相同,行列数互换后代入上式即可.
"同一对角线"的情况比较复杂,假设 ,则同一方向的对角线中,有 条的长度为 (蓝色部分),剩下的两边分别有 条长度递增.
中间的一撮所对应的情况相当于在一个 行 列的棋盘中放置,使得两个皇后在同一行,即 .
两边长度递增的对角线也要按照类似"同一行"的方法推导,即:
但是根据题目的数据范围, 地每次计算是会超时的,考虑展开.
这是一边的长度递增的对角线上的方案数,两边的要乘以二,因为有两个方向,所以最后还要乘以二.