AcWing 1114. 棋盘问题
原题链接
简单
作者:
AC就喝AD钙
,
2024-03-24 23:39:41
,
所有人可见
,
阅读 6
//dfs爆搜,详细见注释
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 8;
int n, k;
char g[N][N];
int res = 0; //记录方案数
//按照每一行枚举,判断该行的每一列是否走过,如果走过就不走了
bool st[N];
//u表示当前枚举到了哪一行,cnt记录放入了几个棋子
void dfs(int u, int cnt)
{
//如果已经放完所有的棋子,退出并方案数+1
if(cnt == k)
{
res ++;
return ;
}
//当前位置如果枚举完棋盘也退出
if(u >= n) return ;
//枚举第u行的第i列
for(int i = 0; i < n; i ++)
{
if(!st[i] && g[u][i] == '#') //第i列没有放过棋子,且这个点是'#'就可以往下搜
{
st[i] = true;
dfs(u + 1, cnt + 1);
st[i] = false;
}
}
//如样例1,如果cnt == k就直接return,不会进入枚举第二行,让它强行访问
dfs(u + 1, cnt);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
while(cin>>n>>k, n > 0 && k > 0)
{
for(int i = 0; i < n; i ++)
cin>>g[i];
res = 0;
dfs(0, 0);
cout<<res<<endl;
}
return 0;
}