食用说明:这是一道DFS题目,如果先前没有接触过这一类的题目,建议可以先看
Macw07的深度优先搜索 DFS:https://www.acgo.cn/discuss/study/19056
正文开始:
题目大意:
要求输出在n*n的棋盘中摆放k个不在棋盘同一行或同一列的棋子的不同方案数
*用字符 #表示可以放棋子的位置,用字符.表示不可以放棋子的位置
题目思路:
利用DFS尝试在每一行放置棋子,并在成功放置k个棋子时,增加answer(方案数)
注意:使用回溯法
*回溯法:适用于这种需要枚举所有可能性的问题。通过递归地尝试每个可能的位置，并在不符合条件时回退。(来源:AC助手)
关键点思考:如何判断某个位置可以放置棋子?
1.确保这个位置所在的行,列都没有其他棋子
如何确保每个棋子在不同行和不同列?
这里,可以使用两个一维数组来记录放置过棋子的行和列:
2.确保此位置本身可以放棋子(确保其为#字符)
解题代码:
