本文最后更新于 702 天前,其中的信息可能已经有所发展或是发生改变。
Original Link
思想:
DFS
。
- 注意棋盘的每一行,每一列及其有棋子存在的对角线的平行线上有且只有一个棋子。
- 递归处理,每一次递视为一次对是否放置棋子的判断,递归的层数视为棋盘的层数,每一层只能放置一个棋子。
- 对于递归的每一层,遍历这层棋盘的格子,判断以该格子的列和对角线的平行线上是否存在过棋子:
- 没有棋子则直接放置,标记并递归进入下一层,以此种方法可以得到最小字典序的方案。
- 放置棋子后,则需要对放置的格子所在的列和对角线的平行线进行标记。
- 递归处理上述过程,直到将所有的棋子放置完毕,记录
res
为方案数,res <= 3
输出当前方案。
- 对于对角线的处理,利用数学关系,将对角线的判断转换为对截距的判断,即放置的棋子的截距各不相同。截距可以数学关系推出
k = i + u
或 k = i - u
,另,由于 i - u
的值可能为负数,因此考虑增加偏移量 k = i - u + n
保证下标合法。
代码:
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| const int N = 110; |
| |
| bool y[N], l[N], r[N]; |
| |
| int n, res; |
| |
| int ans[N]; |
| |
| void dfs(int u){ |
| if(u == n){ |
| res ++; |
| if(res <= 3){ |
| for(int i = 0; i < n; i ++) cout << ans[i] << ' '; |
| cout << endl; |
| } |
| return ; |
| } |
| |
| for(int i = 0; i < n; i ++){ |
| if(!y[i] && !l[u + n + i] && !r[u + n - i]){ |
| y[i] = l[u + n + i] = r[u + n - i] = 1; |
| ans[u] = i + 1; |
| dfs(u + 1); |
| y[i] = l[u + n + i] = r[u + n - i] = 0; |
| } |
| } |
| } |
| |
| void solve(){ |
| cin >> n; |
| dfs(0); |
| cout << res << endl; |
| } |
| |
| int main(){ |
| solve(); |
| return 0; |
| } |