棋盘问题
题目 棋盘问题
思路分析
可以按直接按点枚举
每个点有选与不选两种情况
不选就直接往下一个走（x,y+1) 已放的棋子数cnt保持不变 当然如果走到某行的行末 要跳转到下一行的第一个
然后因为每行只能放一个
所以可以直接枚举行 而不需要行内每个位置都枚举
同样也是选与不选两种方案 不放就跑去下一行cur+1, cnt不变
放的话 得满足 该行的某列是棋盘 且该列没放过 cur+1,cnt+1
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=10;
bool row[N],col[N];
char g[N][N];
int n,k;
int res;
void dfs(int x,int y,int cnt){
if(cnt>k)
return;
if(y==n)
y=0,x++;
if(x==n){
if(cnt==k){
res++;
// for(int i=0;i<n;i++){
// puts(g[i]);
// }
// puts("");
}
return;
}
//不选
dfs(x,y+1,cnt);
//选——首先得是棋盘 其次该点所在行列都没放过
if(g[x][y]=='#' && !row[x] && !col[y]){
row[x]=col[y]=true;
g[x][y]='@';
dfs(x,y+1,cnt+1);
g[x][y]='#';
row[x]=col[y]=false;
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
while(cin>>n>>k,n!=-1,k!=-1){
for(int i=0;i<n;i++)
cin>>g[i];
res=0;
dfs(0,0,0);
cout<<res<<endl;
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=10;
bool col[N];
char g[N][N];
int n,k;
int res;
void dfs(int cur,int cnt){
if(cur==n){
if(cnt==k)
res++;
return;
}
//不选
dfs(cur+1,cnt);
//选——当前行某列为棋盘(#) 且该列没放过
for(int i=0;i<n;i++){
if(g[cur][i]=='#' && !col[i]){
col[i]=true;
g[cur][i]='@';
dfs(cur+1,cnt+1);
g[cur][i]='#';
col[i]=false;
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
while(cin>>n>>k,n!=-1,k!=-1){
for(int i=0;i<n;i++)
cin>>g[i];
res=0;
dfs(0,0);
cout<<res<<endl;
}
return 0;
}
💬 评论