3037: 棋盘问题 简单 DFS 入门题

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
#define ll long long
int n,k; // 定义全局变量n和k，分别表示棋盘的大小和需要放置的棋子数量
char a[10][10]; // 定义一个字符数组a，用于存储棋盘的状态
int xx[10],yy[10]; // 定义两个整型数组xx和yy，用于记录行和列是否可用
int kkk=0; // 定义一个全局变量kkk，用于计数满足条件的方案数
void dfs(int kk){
    if(kk==0){ // 如果不需要再放置棋子
        kkk++; // 计数器加一
        return; // 返回上一层递归
    }
    for(int i=1;i<=n;i++){ // 遍历每一行
        for(int j=1;j<=n;j++){ // 遍历每一列
            if(a[i][j]=='#'&&xx[i]&&yy[j]){ // 如果当前位置可以放置棋子且所在行和列都可用
                xx[i]=0; // 标记当前行不可用
                yy[j]=0; // 标记当前列不可用
                a[i][j]='.'; // 将当前位置标记为已放置棋子
                dfs(kk-1); // 递归调用，继续放置剩余的棋子
                xx[i]=1; // 回溯，恢复当前行可用状态
                yy[j]=1; // 回溯，恢复当前列可用状态
            }
        }
    }
}
int main(){
    while(cin>>n>>k&&n!=-1&&k!=-1){ // 读取输入，直到输入-1 -1为止
        kkk=0; // 初始化计数器
        for(int i=1;i<=n;i++){ // 遍历每一行
            for(int j=1;j<=n;j++){ // 遍历每一列
                cin>>a[i][j]; // 读取棋盘状态
                xx[i]=1; // 初始化行可用状态
                yy[j]=1; // 初始化列可用状态
            }
        }
        dfs(k); // 调用深度优先搜索函数，开始寻找方案
        cout<<kkk<<endl; // 输出满足条件的方案数
    }
    return 0;
}