棋盘挑战
挑战 棋盘
2023-06-13 09:15:37 时间
思想:
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 ++; // 记录答案 res + 1
if(res <= 3){ // 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;
}
相关文章
- Oracle 比率统计:新型分析挑战(oracleratio)
- 挑战MySQL二级考试,提升技能素养(mysql二级考试)
- 系统Linux的多元分支系统:挑战与机遇(linux的分支)
- Oracle学习之路:一步步攻克挑战!(oracle学习课程)
- Linux线程共享:解决编程挑战(linux线程共享)
- Linux用户:解锁挑战(linux用户锁定了)
- MySQL 二进制存储:优势与挑战(mysql二进制数据)
- 用户的数据库性能优化挑战极限Oracle数据库性能优化 超过几十万用户(oracle几十万)
- 2008年MySQL卸载一种新的挑战(2008mysql卸载)
- 试题18道经典MySQL试题挑战你的MySQL知识高度(18道经典mysql)
- 学习Redis,有挑战也有收获(redis 难学吗)