棋盘问题(简单dfs)

发布于 2020-08-30  0 次阅读


题目大意:

棋盘问题
在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。

思路:

直接开一个数组记录访问每行时,被访问过的列
然后dfs每行即可,记得在最后加一个dfs(h+1),避免某行全不满足check后无法进入下一行的问题

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=19;
int n, k;
int flag[N], ans, cnt;
string s[N];

void dfs(int h){
    if(cnt==k)  {ans++; return ;}
    if(h>n) return ;
    for(int i=0; i<n; i++){
        if(!flag[i] && s[h][i]=='#'){
            cnt++, flag[i]=1;
            dfs(h+1);
            cnt--, flag[i]=0;
        }
    }
    dfs(h+1);
}

void solve(){
    while(cin>>n>>k){
        if(n==-1 && k==-1)    break;
        for(int i=1; i<=n; i++) cin>>s[i];
        memset(flag, 0, sizeof(flag)), cnt=ans=0;
        dfs(1);
        cout<<ans<<endl;
    }
    return ;
}       

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    solve();
    return 0;
}

平平无奇的大学在读本科生