01321:棋盘问题

|DFS|回溯|

难点1:DFS，对于dfs(h,t)表示的“即将在第h行进行摆放，已摆放的棋子数为t个”，即如何在dfs函数内部进行递归：若该棋可以放在第h行的第i个位置（标注take[i]=true),则对改行以下行中所有可行的点进行递归。

难点2：回溯算法框架

/* 回溯算法框架 */
void backtrack(State *state, vector<Choice *> &choices, vector<State *> &res) {// 判断是否为解if (isSolution(state)) {// 记录解recordSolution(state, res);// 不再继续搜索return;}// 遍历所有选择for (Choice choice : choices) {// 剪枝：判断选择是否合法if (isValid(state, choice)) {// 尝试：做出选择，更新状态makeChoice(state, choice);backtrack(state, choices, res);// 回退：撤销选择，恢复到之前的状态undoChoice(state, choice);}}
}

https://www.cnblogs.com/Ayanowww/p/11555193.html
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>using namespace std;int n,k,res;
char chess[10][10];
bool take[10];  //用于判断该列是否已有棋子//用空间换时间void dfs(int h,int t){//h为即将探索的行数，t为已经摆放的个数if(t==k){res++;return;}if(h==n){return;//回溯，重新探索}for(int i=h;i<n;i++){for(int j=0;j<n;j++){if(chess[i][j]=='#'&&!take[j]){take[j] = true;dfs(i+1,t+1);take[j] = false;//结合回溯算法框架理解}}}
}int main(){while(cin>>n>>k){if(n==-1&&k==-1){break;}for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>chess[i][j];}}for(int i=0;i<n;i++){take[i] = false;}res = 0;dfs(0,0);cout<<res<<endl;}return 0;
}